使单个函数在列表,ByteStrings和文本(以及可能的其他类似表示)上工作

Question

我正在编写一个函数,可以在一系列任意符号中进行搜索.我想使它足够通用,以便它可以在列表,Foldables以及ByteStrings和Texts上运行.将其概括Foldable为简单.但是如何包含ByteStrings和Texts？当然我可以转换ByteString成一个列表,然后调用我的功能,但我会失去所有的优势ByteString.

举一个具体的例子,假设我们想要制作直方图函数:

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一劳永逸地写？

Answer 1

您的解决方案几乎就是ListLike包的功能.还有一些额外的包listlike-instances,它们为Text和添加实例Vector.

Answer 2

过了一会儿我自己做了一个解决方案,但是我不确定它是否能以更好的方式解决,或者是否有人已经在某个库中做过这个.

我用TypeFamiliesas 创建了一个类型类

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等上使用它

• 还有另一种(也许更简单)的方法吗？
• 是否有一些库可以解决这个问题(以这种方式或另一种方式)？

Answer 3

您可能会考虑将折叠物本身对象化:

{-# 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