Foldable

We gaan eens een datatype verzinnen zie

Niet-lege lijsten:

data NietLeeg a = Cons a (Maybe (NietLeeg a))

vorm datatype geeft aanleiding tot functor:

class Functor f where
    fmap :: (a -> b) -> (f a -> f b)

instance Functor NietLeeg where
    fmap f (Cons waarde rest) = Cons (f a) (fmap f <$> rest)

Definitie van Foldable

class Foldable t where
    -- een van deze twee is genoeg
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr   :: (a -> b -> b) -> b -> t a -> b

• foldMap:
  • neem een monoïde m
  • gooi alle waarden uit de structuur t in die monoïde
  • voeg dan alles lineair samen
• foldr: zoals gewoonlijk

geen echte 'wetten' zoals er bij Functor en Applicative zijn

Hoe schrijf je een Foldable-implementatie?

Ik vind foldMap het makkelijkste.

Centrale vraag:

• Hoe beschouw ik de elementen van mijn datastructuur één per één?
• Hoe pas ik de monoïdale operator <> op die elementen toe?

Foldable voor NietLeeg

instance Foldable NietLeeg where
  foldMap :: (Monoid m) => (a -> m) -> NietLeeg a -> m
  foldMap naarMonoïde (Cons waarde rest) = 

Foldable voor NietLeeg

instance Foldable NietLeeg where
  foldMap :: (Monoid m) => (a -> m) -> NietLeeg a -> m
  foldMap naarMonoïde (Cons waarde Nothing) = naarMonoïde waarde
  foldMap naarMonoïde (Cons waarde (Just rest)) = naarMonoïde waarde <> foldMap naarMonoïde rest

Kleine divertissement: de maybe-functie

maybe :: b -> (a -> b) -> Maybe a -> b

Dus opsplitsen in Nothing en Just rest is niet nodig:

maybe mempty (foldMap naarMonoïde) rest

is precies het goede element om mee te rechtsvermenigvuldigen.

Foldable voor NietLeeg

instance Foldable NietLeeg where
  foldMap :: (Monoid m) => (a -> m) -> NietLeeg a -> m
  foldMap naarMonoïde (Cons waarde rest) 
    = naarMonoïde waarde <> maybe mempty (foldMap naarMonoïde) rest

Wat koop je met Foldable?

Stel dat Foldable t. Dan:

• foldMap :: Monoid m => (a -> m) -> t a -> m
• foldr :: (a -> b -> b) -> b -> t a -> b

zijn minimaal (de één levert de ander). Maar ook gratis zijn:

• fold :: Monoid m => t m -> m
• foldl :: (b -> a -> b) -> b -> t a -> b
• toList :: t a -> [a]
• null :: t a -> Bool
• length :: t a -> Int
• elem :: Eq a => a -> t a -> Bool
• maximum :: Ord a => t a -> a
• minimum :: Ord a => t a -> a
• sum :: Num a => t a -> a
• product :: Num a => t a -> a

Traversable

Definitie van Traversable

class (Functor t, Foldable t) => Traversable where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)

wtf?

• traverse:

  • voor een bepaalde applicatieve functor f,
  • neem een waarde van type a en maak er een b binnen f van
  • doe dat voor elke waarde van de structuur
  • geef diezelfde structuur terug, in een f

• sequenceA:

  • voor een bepaalde applicatieve functor f,
  • neem een structuur vol f a's
  • pas ze allemaal toe ("van links naar rechts")
  • hul het resultaat in een f

Definitie van Traversable

traverse is een soort map met effecten.

(denk aan Maybe, Either, State, [], ...)

Traversable is voor Applicative wat Foldable is voor Monoid.

• traverse f = sequenceA . fmap f
• sequenceA = traverse id

Hoe schrijf je een Traversable-implementatie?

Basically gwn foldMap maar met traverse

Maar vaak gepruts met de waarde in de functor krijgen!

instance Traversable NietLeeg where
  traverse :: (Applicative f) => (a -> f b) -> NietLeeg a -> f (NietLeeg b)
  traverse naarApp (Cons waarde Nothing) = (`Cons` Nothing) <$> naarApp waarde
  traverse naarApp (Cons waarde (Just rest)) = Cons <$> naarApp waarde <*> (Just <$> traverse naarApp rest)

Maar Maybe is zelf ook een Traversable!

instance Traversable NietLeeg where
  traverse :: (Applicative f) => (a -> f b) -> NietLeeg a -> f (NietLeeg b)
  traverse naarApp (Cons waarde rest) = Cons <$> naarApp waarde <*> traverse (traverse naarApp) rest