让一个单一函数能够在列表、字节串和文本（以及可能的其他类似表示）上工作

Question

我正在编写一个函数，用于在任意符号序列中进行搜索。我希望使其足够通用，可以在列表、Foldable以及ByteString和Text上运行。将其泛化到Foldable很简单。但如何包括ByteString和Text呢？当然，我可以将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和

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

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

在像Haskell这样的函数式语言中，人们不会期望出现这种情况。

如何使其通用化，一次编写histogram并永久使用？

- Petr

---

你总是提出有趣的问题，因为你深思熟虑自己正在做什么，并且总是想要更多地了解。+1 - AndrewC

Answer 1

你的解决方案与ListLike包几乎相同。此外，还有一个额外的包listlike-instances，它为Text和Vector添加了实例。

- shang

Answer 2

一段时间后，我自己想出了一个解决方案，但我不确定是否可以用更好的方式解决，或者是否有人已经在某个库中实现了这个。

我使用创建了一个类型类。

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

并在Foldable、ByteString、Text等上使用它。

• 是否有另一种（可能更简单的）方法来实现这个？
• 是否有一些库来解决这个问题（以这种或其他方式）？

- Petr

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

- applicative

---

虽然这可能不是我要走的路，但它非常有趣。绝对值得探索。我也相信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)，我简要检查了一下法律，似乎是有效的。这可以提供更多的方法来组合其操作。 - Petr

有趣的是，这当然是可应用的——这是Rabkin在讨论中的目的，正如评论中所指出的那样。我忘了提到伟大的Conal Elliot的许多帖子，例如http://conal.net/blog/posts/proofs-for-left-fold-zipping，跟随Rabkin，我还没有完全阅读。他和Rabkin似乎并不太关注这里的问题，即“Fold”类型与列表无关，但可以应用于任何串行类型X，只要有一个通用的“foldX”函数。我最初是从`sdcvvc`在这里的评论中了解到的https://dev59.com/UWgv5IYBdhLWcg3wKtpB - applicative

Answer 4

我发现另一种使用 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

- Petr