Заставить одну функцию работать со списками, ByteStrings и Texts (и, возможно, с другими подобными представлениями)

Я пишу функцию, которая выполняет поиск в последовательности произвольных символов. Я хотел бы сделать его достаточно общим, чтобы он работал со списками, Foldable, а также с ByteString и Text. Обобщить его до Foldable просто. Но как включить ByteStrings и Texts? Конечно, я мог бы преобразовать ByteString в список, а затем вызвать свою функцию, но я потерял бы все преимущества ByteStrings.

Чтобы иметь конкретный пример, скажем, мы хотим сделать функцию гистограммы:

import Control.Monad.State
import qualified Data.Foldable as F
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Word
import qualified Data.ByteString as B
import qualified Data.Text as T

type Histogram a = Map a Int

empty :: (Ord a) => Histogram a
empty = Map.empty

histogramStep :: (Ord a) => a -> Histogram a -> Histogram a
histogramStep k = Map.insertWith (+) k 1

histogram :: (Ord a, F.Foldable t) => t a -> Histogram a
histogram = F.foldl (flip histogramStep) empty

Но поскольку ни ByteString, ни Text не могут быть Foldable (он хранит только Word8s/Chars, а не произвольные элементы), я застрял в создании дополнительных функций, которые выглядят точно как предыдущая, только с другим типом подписи:

histogramBS :: B.ByteString -> Histogram Word8
histogramBS = B.foldl (flip histogramStep) empty

histogramText :: T.Text -> Histogram Char
histogramText = T.foldl (flip histogramStep) empty

Это то, чего нельзя ожидать от функционального языка, такого как Haskell.

Как сделать его общим, написать histogram раз и навсегда?


text fold haskell lenses bytestring
person Petr    schedule 12.10.2012    source источник
comment
Вы всегда задаете интересные вопросы, потому что глубоко думаете о том, что делаете, и всегда хотите понять больше. +1   -  person AndrewC    schedule 12.10.2012

Ответы (4)


arrow_upward
9
arrow_downward

Ваше решение во многом похоже на то, что делает пакет ListLike. Существует также дополнительный пакет listlike-instances, который добавляет экземпляры для Text и Vector. .

person shang    schedule 12.10.2012

arrow_upward
5
arrow_downward

Через некоторое время я сам сделал решение, но не уверен, что его можно было решить лучше, или кто-то уже сделал это в какой-то библиотеке.

Я создал класс типов с TypeFamilies как

class Foldable' t where
    type Element t :: *
    foldlE :: (b -> Element t -> b) -> b -> t -> b
    -- other functions could be copied here from Foldable

и экземпляры:

newtype WrapFoldable f a = WrapFoldable { unwrapFoldable :: f a }
instance (F.Foldable f) => Foldable' (WrapFoldable f a) where
    type Element (WrapFoldable f a) = a
    foldlE f z = F.foldl f z . unwrapFoldable

instance Foldable' B.ByteString where
    type Element B.ByteString = Word8
    foldlE = B.foldl


instance Foldable' T.Text where
    type Element (T.Text) = Char
    foldlE = T.foldl

или еще лучше с FlexibleInstances:

instance (F.Foldable t) => Foldable' (t a) where
    type Element (t a) = a
    foldlE = F.foldl

Теперь я могу написать (с FlexibleContexts):

histogram :: (Ord (Element t), Foldable' t) => t -> Histogram (Element t)
histogram = foldlE (flip histogramStep) empty

и используйте его на Foldables, ByteStrings, Texts и т. д.

  • Есть ли другой (возможно, более простой) способ сделать это?
  • Есть ли какая-нибудь библиотека, решающая эту проблему (так или иначе)?
person Petr    schedule 12.10.2012

arrow_upward
5
arrow_downward

Вы можете рассмотреть возможность объективации самих складок:

{-# LANGUAGE GADTs #-}
import Data.List (foldl', unfoldr)
import qualified Data.ByteString.Lazy as B
import qualified Data.Vector.Unboxed as V
import qualified Data.Text as T
import qualified Data.Map as Map
import Data.Word
type Histogram a = Map.Map a Int

empty :: (Ord a) => Histogram a
empty = Map.empty
histogramStep :: (Ord a) => Histogram a -> a -> Histogram a
histogramStep h k = Map.insertWith (+) k 1 h 

histogram :: Ord b => Fold b (Histogram b)
histogram = Fold histogramStep empty id

histogramT :: T.Text -> Histogram Char
histogramT = foldT histogram
histogramB :: B.ByteString -> Histogram Word8
histogramB = foldB histogram 
histogramL :: Ord b => [b] -> Histogram b
histogramL = foldL histogram

-- helper library
-- see http://squing.blogspot.fr/2008/11/beautiful-folding.html
-- note existential type
data Fold b c where  Fold ::  (a -> b -> a) -> !a -> (a -> c) -> Fold b c
instance Functor (Fold b) where  fmap f (Fold op x g) = Fold op x (f . g)

foldL :: Fold b c -> [b] -> c
foldL (Fold f x c) bs = c $ (foldl' f x bs)

foldV :: V.Unbox b => Fold b c -> V.Vector b -> c
foldV (Fold f x c) bs = c $ (V.foldl' f x bs)

foldT :: Fold Char t -> T.Text -> t
foldT (Fold f x c) t = c $ (T.foldl' f x t)

foldB :: Fold Word8 t -> B.ByteString -> t
foldB (Fold f x c) t = c $ (B.foldl' f x t)


sum_, product_ :: Num a => Fold a a
sum_ = Fold (+) 0 id
product_ = Fold (*) 1 id

length_ :: Fold a Int
length_ = Fold (const . (+1)) 0 id
maximum_ = Fold max 0 id
person applicative    schedule 12.10.2012
comment
Хотя это, вероятно, не тот путь, по которому я пойду, это очень интересно. Определенно стоит изучить. Я тоже считаю, что Fold - это комонада: instance Comonad (Fold b) where extract (Fold _ x r) = r x ; duplicate (Fold f x r) = Fold f x (\y -> Fold f y r), бегло проверил законы и вроде действителен. Это могло бы дать больше способов, как совмещать свои операции. - person Petr; 12.10.2012
comment
Интересно; это, конечно, аппликативно - это было целью Рабкина при его обсуждении, как отмечается в комментариях. Я забыл упомянуть множество постов великого Конала Эллиота, например. conal.net/blog/posts/proofs-for-left-fold- zipping, вслед за Рабкиным, который я не до конца прочитал. Он и Рабкин, кажется, не придают особого значения тому факту, о котором здесь идет речь, что тип Fold не имеет ничего общего со списками, но может быть применен к любому последовательному типу X, учитывая общую функцию foldX. Впервые я узнал об этом из комментария sdcvvc здесь stackoverflow.com/questions/10803221. - person applicative; 14.10.2012

arrow_upward
2
arrow_downward

Я нашел другое решение, используя пакет lens, который имеет подробную иерархию классов типов, определяющую различные типы данных. структуры. Его подход аналогичен подходу в аппликативном ответе - он объективирует складки:

{-# LANGUAGE RankNTypes #-}
import Control.Monad.State
import qualified Data.Foldable as F
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import Data.Word
import qualified Data.ByteString as B
import qualified Data.Text as T

import Control.Lens.Fold
import qualified Data.ByteString.Lens as LBS
import qualified Data.Text.Lens as LT

type Histogram a = Map a Int

empty :: (Ord a) => Histogram a
empty = Map.empty

histogramStep :: (Ord a) => a -> Histogram a -> Histogram a
histogramStep k = Map.insertWith (+) k 1

-- Histogram on anything that can be folded into `a`:

histogram :: (Ord a) => Fold c a -> c -> Histogram a
histogram f = foldlOf f (flip histogramStep) empty

-- Specializations are simple:

histogramF :: (Ord a, F.Foldable t) => t a -> Histogram a
histogramF = histogram folded

histogramBS :: B.ByteString -> Histogram Word8
histogramBS = histogram LBS.bytes

histogramText :: T.Text -> Histogram Char
histogramText = histogram LT.text
person Petr    schedule 19.10.2012