CODEWITHSUNDEEP
recursion-schemescatamorphism
P Varga
P Varga

Reputation: 20229

Morphism where the algebra receives the item's position

Which one is the appropriate morphism (recursion scheme) to use when the given item's position (index, or path) is required in the transformer function?

A simple example would be transforming a list ["foo", "bar", "qux"] into the string "foo, bar, and qux". The current element's position is needed to know when to insert the and.

Upvotes: 1

Views: 55

Answers (1)

michid
michid

Reputation: 10814

You need to make the index part of the structure so it is available to the recursion scheme. An ad-hoc way to do this is to define a foldWithIndex function:

foldWithIndex :: (Foldable t, Num i) => (i -> a -> b -> b) -> b -> t a -> b
foldWithIndex f z t = snd $ foldr f' (0, z) t
    where
        f' z (i, x) = (i + 1, f i z x)

This function takes an operator for combining the elements which also considers the index:

foldWithIndex combine "" ["foo", "bar", "qux"]
    where
        combine 0 s1 s2 = s1 ++ s2
        combine 1 s1 s2 = s1 ++ " and " ++ s2
        combine _ s1 s2 = s1 ++ ", " ++ s2

results in "foo, bar and qux".

For a more general approach see Data.Foldable.WithIndex, which provides a foldable typeclass that also takes an index into account.

Upvotes: 1

Related Questions