Eine einzelne Funktion an Listen, ByteStrings und Texten (und vielleicht anderen ähnlichen Darstellungen) arbeiten lassen

Question

Ich schreibe eine Funktion, die einige Suchvorgänge in einer Abfolge beliebiger Symbole durchführt. Ich möchte es generisch genug machen, so dass es auf Listen, Foldable s sowie auf ByteString s und Text s funktioniert. Verallgemeinern es zu Foldable ist einfach. Aber wie kann man ByteString s und Text s einschließen? Sicher könnte ich ByteString in eine Liste umwandeln und dann meine Funktion anrufen, aber ich würde alle Vorteile verlieren ByteString s.

ein konkretes Beispiel haben, lassen Sie uns sagen, dass wir eine Histogramm-Funktion machen wollen:

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 

Da aber weder ByteString noch Text Foldable (es speichert nur Word8 s/Char s, nicht beliebige Elemente) können, ich bin mit dem Erstellen von mehr Funktionen stecken, die vor genau wie die aussehen, nur mit einer anderen Art Unterschriften:

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

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

diese ist etwas, was man in einer funktionalen Sprache wie Haskell nicht erwartet.

Wie man es generisch macht, histogram ein für allemal zu schreiben?

Answer 1

Ihre Lösung ist so ziemlich das, was das ListLike Paket tut. Es gibt auch das zusätzliche Paket listlike-instances, das Instanzen für Text und Vector hinzufügt.

Answer 2

Nach einer Weile habe ich selbst eine Lösung gefunden, aber ich bin nicht sicher, ob es besser gelöst werden könnte, oder ob jemand das schon in einer Bibliothek getan hat.

Ich habe eine Typklasse mit TypeFamilies als

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

und Instanzen:

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 

oder noch besser mit FlexibleInstances:

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

Jetzt kann ich schreiben (mit FlexibleContexts):

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

und verwenden Sie es auf Foldable s, ByteString s, Text s usw.

• Gibt es eine andere (vielleicht einfacher) Weg, es zu tun?
• Gibt es eine Bibliothek, die dieses Problem anspricht (auf diese oder andere Weise)?

Answer 3

Sie objektivierenden betrachten könnten Falten selbst:

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

ich eine andere Lösung mit lens Paket gefunden, die eine detaillierte Typklassenhierarchie identifizieren andere Art von Datenstrukturen hat. Sein Ansatz ähnelt dem in der Antwort von applicative - es objektiviert Falten:

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