Tworzenie pojedynczej funkcji działa na listach, ByteStringach i tekstach (i być może na innych podobnych reprezentacjach)

Question

Piszę funkcję, która wykonuje wyszukiwanie w sekwencji dowolnych symboli. Chciałbym uczynić go generycznym na tyle, aby działał na listach, Foldable s oraz na ByteString s i Text s. Uogólnienie go na Foldable jest proste. Ale jak dołączyć ByteString s i Text s? Pewnie mógłbym zamienić ByteString na listę, a następnie zadzwonić do mojej funkcji, ale straciłbym wszystkie zalety ByteString s.

mieć konkretny przykład załóżmy, że chcemy, aby funkcja histogramu:

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 

ale ponieważ ani ByteString ani tekst można Foldable (Przechowuje tylko Word8 s/Char s, a nie arbitralne elementy), Utknąłem z tworzeniem więcej funkcji, które wyglądają dokładniejak jeden przed, tylko z różnymi podpisami typu:

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

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

ten jest czymś, czego się nie spodziewa w tak funkcjonalnym języku jak Haskell.

Jak zrobić to ogólne, aby napisać histogram raz na zawsze?

Answer 1

Twoje rozwiązanie jest dokładnie tym, co robi pakiet ListLike. Dostępny jest również dodatkowy pakiet listlike-instances, który dodaje instancje dla Text i Vector.

Answer 2

Po pewnym czasie sam opracowałem rozwiązanie, ale nie jestem pewien, czy można go rozwiązać w lepszy sposób, czy też ktoś już to zrobił w jakiejś bibliotece.

stworzyłem typu klasę z TypeFamilies jak

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

i przypadkach:

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 

lub jeszcze lepiej z FlexibleInstances:

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

Teraz mogę napisać (z FlexibleContexts):

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

i używać go na Foldable s, ByteString s, Text s itp

• Czy istnieje inny (być może prostszy) sposób to zrobić?
• Czy istnieje biblioteka, która rozwiązuje ten problem (w ten czy inny sposób)?

Answer 3

Można rozważyć objectifying składa się:

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

Answer 4

znalazłem inne rozwiązanie korzystając lens pakiet, który ma szczegółowy typ klasy hierarchii identyfikujące różnego rodzaju struktur danych. Jego podejście jest podobne do odpowiedzi aplikacyjnej - obiektywizuje fałdy:

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