How many for-loop-like higher-order-functions does Haskell have?

Learn
#1

Just curious, because today was the first time I used mapAccumL (to do a Vigenere cipher where the cipher was stored as an infinite list of offsets), but I’ve had experience with mapAccumM, when it comes to more esoteric for-loop likes.

Is there a master list or a blog post on all the higher order functions Haskell uses where other languages might use for loops? Of course, this isn’t “all higher order functions”; ($) and (.), for instance are HoFs, and (>>=) on deterministic types isn’t loop-like.

It’d also be interesting to have a list of loop-like HOFs because it’d help us figure out if we’re missing any loop-like HOFs.

Point of this is, at a certain point in time, the HOF approach to loop-like behavior might become predominant and the older while / for loops might end up becoming regarded as smelly as goto. From MondayMorningHaskell, it appears that in C++, replacing your for loops with template metaprogramming loop replacement has already become a thing.

It’s also a useful riposte to FP-lite advocates who think FP simplifies to map, filter, and reduce. That is to say, the family of loop-like HOFs is far larger than simply map, filter, and reduce, and you probably should learn Haskell to understand what FP is really about.

#2

I have nothing clever to add, I just want to be the first to say traverse, which is my favorite superpower.

2 Likes
#3

Not in the standard library, or in common use, but I’m a huge fan of

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo f g = go where go = f . fmap go . g
4 Likes
#4

I think infinite? Because they can be so domain-specific.

For instance, apecs has cmap and friends (and you can come up with your own that build on them too!)

1 Like
#5

Oh seconded, because too I love doing terrible things to hylo, like this:

phylo
    :: (IndexedFunctor f)
    => (Index f -> path -> path)
    -> (path -> f b -> b)
    -> (path -> a -> f a)
    -> path
    -> a -> b
phylo cons alg coalg = h where
    h p = alg p . imap (\ i -> h (cons i p)) . coalg p
3 Likes
#6

And probably worth pointing out that mapAccumM is “just” an application of traverse with a particular usage of StateT.

#7

TBH this amounts more to an ontology of for loops.

Recursion is more powerful than for loops, being equivalent in power to while loops, but it’s more interesting what specific for loop types there are.

And recursion schemes basically cover all possible for loops.

1 Like
#8

recursion schemes basically cover all possible for loops.

It’s not just “basically”, and it’s not restricted to for loops. You can get fix from recursion schemes, at which point you have arbitrary recursion

fix :: (a -> a) -> a
fix = hylo (uncurry ($)) (\x -> (x,x))
4 Likes