9

我正在编写一个函数，该函数在一系列任意符号中进行一些搜索。我想让它足够通用，以便它适用于列表、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一劳永逸地编写？

4

4 回答 4

9

您的解决方案几乎就是ListLike包所做的。还有额外的包listlike-instances为Text和添加实例Vector。

于 2012-10-12T11:15:26.590 回答
5

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

TypeFamilies我用as创建了一个类型类

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 等。

  • 还有另一种（可能更简单）的方法吗？
  • 是否有一些图书馆可以解决这个问题（以这种或另一种方式）？
于 2012-10-12T11:00:27.247 回答
5

您可能会考虑将折叠本身客观化：

{-# 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
于 2012-10-12T16:45:17.420 回答
2

我找到了另一个使用lens包的解决方案，它有一个详细的类型类层次结构来识别不同类型的数据结构。它的方法类似于 applicative 的答案 - 它客观化折叠：

{-# 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
于 2012-10-19T10:01:53.410 回答