Направете една функция да работи върху списъци, байтови низове и текстове (и може би други подобни представяния)

Пиша функция, която извършва известно търсене в поредица от произволни символи. Бих искал да го направя достатъчно общ, така че да работи на списъци, Foldables, както и на ByteStrings и Texts. Обобщаването му до Foldable е просто. Но как да включите ByteStrings и Texts? Разбира се, че мога да конвертирам ByteString в списък и след това да извикам моята функция, но бих загубил всички предимства ByteStrings.

За да имаме конкретен пример, нека кажем, че искаме да направим функция хистограма:

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, нито Text могат да бъдат Foldable (съхранява само Word8s/Chars, а не произволни елементи), аз съм прикован към създаването на повече функции, които изглеждат точно като предишната, само с различен тип подписи:

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

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

Това е нещо, което човек не очаква във функционален език като Haskell.

Как да го направя общ, да напиша histogram веднъж завинаги?


text fold haskell lenses bytestring
person Petr    schedule 12.10.2012    source източник
comment
Винаги задавате интересни въпроси, защото мислите дълбоко за това, което правите и винаги искате да разберете повече. +1   -  person AndrewC    schedule 12.10.2012

Отговори (4)


arrow_upward
9
arrow_downward

Вашето решение е почти това, което прави пакетът ListLike. Има и допълнителния пакет listlike-instances, който добавя екземпляри за Text и Vector .

person shang    schedule 12.10.2012

arrow_upward
5
arrow_downward

След известно време сам направих решение, но не съм сигурен дали може да бъде решено по-добър начин или някой вече го е правил в някоя библиотека.

Създадох тип-клас с TypeFamilies като

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 и т.н.

  • Има ли друг (може би по-прост) начин да го направите?
  • Има ли библиотека, която решава този проблем (по този или друг начин)?
person Petr    schedule 12.10.2012

arrow_upward
5
arrow_downward

Може да помислите за обективизиране на самите гънки:

{-# 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
person applicative    schedule 12.10.2012
comment
Въпреки че това вероятно не е начинът, по който ще тръгна, е много интересно. Определено си струва да се проучи. Също така вярвам, че 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), проверих накратко законите и изглеждат валидни. Това може да даде повече начини за комбиниране на неговите операции. - person Petr; 12.10.2012
comment
Интересно; това, разбира се, е апликативно -- това беше целта на Рабкин при обсъждането му, както е отбелязано в коментарите. Забравих да спомена многото публикации на великия Конал Елиът, напр. conal.net/blog/posts/proofs-for-left-fold- zip, след Рабкин, който не съм прочел напълно. Той и Рабкин изглежда не обръщат особено внимание на въпросния факт тук, че типът Fold няма нищо общо със списъците, но може да се приложи към всеки сериен тип X, като се има предвид обща foldX функция. За първи път научих за това от коментара на sdcvvc тук stackoverflow.com/questions/10803221 - person applicative; 14.10.2012

arrow_upward
2
arrow_downward

Намерих друго решение, използвайки пакета 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
person Petr    schedule 19.10.2012