9

任意のシンボルのシーケンスで検索を行う関数を作成しています。Foldableリストやs だけでなくByteStrings やs でも機能するように、十分に一般的なものにしたいと思いますText。それを一般化するの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

しかし、ByteStringText も Text もできないため(任意の要素ではなくs/ sFoldableのみを格納する)、型シグネチャが異なるだけで、以前のものとまったく同じように見える関数をさらに作成することに行き詰まっています。Word8Char

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-instancesTextもありますVector。

于 2012-10-12T11:15:26.590 に答える
5

しばらくして自分で解決策を作成しましたが、より良い方法で解決できるかどうか、または誰かがすでにライブラリでこれを行っているかどうかはわかりません。

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などで使用します。

  • それを行う別の（おそらくもっと簡単な）方法はありますか？
  • この問題に対処するライブラリはありますか (この方法または別の方法で)。
于 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's answer のものと似ています - それは折り目を客観化します:

{-# 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 に答える