Haskell folding nested lists

Question

Currently I'm messing around with Haskell. My knowledge about Haskell (and functional languages in general) is still low but I'm working on it. What really bothers me is a (as I thought) simple task: folding nested lists with one fold per depth.

fcalc = foldr (\x y -> (foldr (**) 1 x) * (foldr (**) 1 y)) [1.0, 1.0] [[2.0, 3.0], [4.0, 5.0]]

What it should do: 2^3 * 4^5 where the ^ is done by the lambda'd inner folds. Sadly it does not work.

Occurs check: cannot construct the infinite type: t0 = [t0]
In the third argument of `foldr', namely `y'

I've read a bit about the given "infinite type" error mainly indicating that a variable is used as e.g. element while it was a list instead. This made me thinking about the second param of the outer foldr as the problem but without success. I just don't get it. :/

Well, I wonder if you aren't going the wrong way about this. First of all, you're breaking one of my rules of thumb: you don't use folds to solve a problem directly, you use them to implement some intermediate abstraction to solve your problem. Second, I wonder if lists and nested lists are really the correct data structure for what you're trying to do; I get the feeling that you're dealing with a problem area better served by some sort of abstract syntax tree. — Luis Casillas

Lily Ballard Lily Ballard · Accepted Answer · 2012-02-02T20:16:32

Your problem is that you're trying to do the a^b calculation on your accumulator inside the fold, while also doing it on each element. What you really want is something like

fcalc = foldr (\x y -> (foldr (**) 1 x) * y) 1 [[1.0, 1.0], [2.0, 3.0], [4.0, 5.0]]

Remember, the output of each step of foldr is plugged in as the second argument of the next step (e.g. the y variable in this case). Since your foldr step is returning a number, the y variable is already a number, and therefore you can't fold over it.

Haskell folding nested lists

2 Answers