Esecuzione di una singola funzione su elenchi, ByteStrings e testi (e forse altre rappresentazioni simili)

Question

Sto scrivendo una funzione che esegue una ricerca in una sequenza di simboli arbitrari. Mi piacerebbe renderlo abbastanza generico in modo che funzioni sugli elenchi, Foldable s su ByteString s e Text s. Generalizzarlo a Foldable è semplice. Ma come includere ByteString se Text s? Certo, potrei convertire ByteString in una lista e quindi chiamare la mia funzione, ma perderei tutti i vantaggi ByteString s.

Per avere un esempio concreto diciamo che vogliamo fare una funzione istogramma:

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 

Ma poiché né ByteString né testo può essere Foldable (esso memorizza solo Word8 s/Char s, non elementi arbitrari), sono bloccato con la creazione di più funzioni che sembrano esattamente come il precedente, solo con un diverso tipo di firme:

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

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

Questo è qualcosa che non ci si aspetta in un linguaggio funzionale come Haskell.

Come renderlo generico, per scrivere histogram una volta per tutte?

Answer 1

La tua soluzione è praticamente ciò che fa il pacchetto ListLike. C'è anche il pacchetto aggiuntivo listlike-instances che aggiunge istanze per Text e Vector.

Answer 2

Dopo un po 'ho risolto io stesso una soluzione, ma non sono sicuro che potrebbe essere risolto in un modo migliore, o se qualcuno lo ha già fatto in qualche biblioteca.

Ho creato un tipo di classe con TypeFamilies come

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

e istanze:

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 

o meglio ancora con FlexibleInstances:

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

ora posso scrivere (con FlexibleContexts):

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

e usarlo su Foldable s, ByteString s, Text s ecc

• C'è un altro (forse più semplice) modo per farlo?
• C'è qualche libreria che risolve questo problema (in questo modo o in un altro)?

Answer 3

Si potrebbe considerare oggettivante si piega:

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

ho trovato un'altra soluzione con lens pacchetto, che ha una dettagliata gerarchia di tipo classe identificare diversi tipi di strutture di dati. Il suo approccio è simile a quello in risposta applicativa - è oggettiva pieghe:

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