Implement a fold-like Function in Haskell

Question

Let's say I need to write a function that applies a function to each item in a List, and then appends it to an accumulator. When the List is empty, return the accumulator.

go :: [a] -> (a -> [b]) -> [b] -> [b]
go [] f acc = acc
go (x:xs) f acc = go xs f (acc ++ f x)

myFold :: [a] -> (a -> [b]) -> [b]
myFold as f = go as f []

I used the go function so that I wouldn't force the myFold caller to have to provide an empty [b] type. Also, I used the go function to achieve tail recursion.

In Scala, I would've put @annotation.tailrec to make the compilation fail if the compiler could not perform tail-call optimization.

Is the above code idiomatic in Haskell?

Answer 1

First, your function is concatMap from Prelude.

More idiomatic ways to write it:

myFold :: (a -> [b]) -> [a] -> [b]
myFold = concat . map
-- or
myFold f = foldr (\x acc -> (f x) ++ acc) []

If efficiency is a concern, it's a completely different question. Recommended steps in priority order:

1. Always compile at least with -O2
2. Lists are slow. ++ operation especially. Consider Data.Sequence or even vectors.
3. Avoid lazyness in your types
4. Provide all small functions with INLINE pragma.
5. And more...

Answer 2

You're definitely on the right track here for producing good Haskell code, assuming you're intentionally avoiding Prelude functions in favor of exercising other skills!

The very first thing I would change is the order of arguments in your myFold function (and by extension go), i.e., pass the function to map over the list in the first position. This can help you be terse when calling it elsewhere in your code. For instance, consider these two trivial definitions of the same identity function.

listid :: [a] -> [a]
listid as = myFold as (:[])

listid' = myFold' (:[]) -- Implies an instance of myFold w/ arguments flipped

The second definition is written in pointfree style. This is considered good practice (in moderation) due to its emphasis on composing functionality over moving data around.

The next thing I would address is hiding your helper function go by making it locally defined in myFold.

myFold f as = go ...
    where go f as acc = ...

This has a few benefits.

1. If you're writing a library module here by default go will end up being exported to all of your users. Since this is an anonymous helper function, you probably don't want that.
2. Because again this is a one-shot helper function, locally defining it for myFold keeps it close to where it's used as opposed to floating around the top-level elsewhere.

That's about as idiomatic as you'll get without using Prelude functions. It is good to note however that your function is the composition of concat and map, and reusing functions from the Prelude is almost always better for readability.