Haskell Foldr ADT from a List of Expressions into a single expression

Question

So this is the data definition and my function.

Task 3

Define addAll, which adds a list of expressions together into a single expression without introducing any 'junk'.

You could use foldr since it reduces a list into a single expression.

Data definition and function

data Expr = Op BinOp Expr Expr | NumLit Int | ExpX Int deriving (Eq, Show) data BinOp = AddOp | MulOp deriving (Eq, Show) addAll :: [Expr] -> Expr addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty where empty = NumLit 3

Error message

src/Simplify.hs:31:16: error: [GHC-83865] • Couldn't match expected type ‘Expr’ with actual type ‘t0 (t1 a0) -> t1 a0’ • Probable cause: ‘foldr’ is applied to too few arguments In the expression: foldr (\ x acc -> if null acc then x else add x acc) empty In an equation for ‘addAll’: addAll exprs = foldr (\ x acc -> if null acc then x else add x acc) empty where empty = NumLit 3 | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ src/Simplify.hs:31:56: error: [GHC-83865] • Couldn't match expected type ‘t1 a0’ with actual type ‘Expr’ • In the expression: add x acc In the expression: if null acc then x else add x acc In the first argument of ‘foldr’, namely ‘(\ x acc -> if null acc then x else add x acc)’ • Relevant bindings include acc :: t1 a0 (bound at src/Simplify.hs:31:25) x :: t1 a0 (bound at src/Simplify.hs:31:23) | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty | ^^^^^^^^^ src/Simplify.hs:31:60: error: [GHC-83865] • Couldn't match expected type ‘Expr’ with actual type ‘t1 a0’ • In the first argument of ‘add’, namely ‘x’ In the expression: add x acc In the expression: if null acc then x else add x acc • Relevant bindings include acc :: t1 a0 (bound at src/Simplify.hs:31:25) x :: t1 a0 (bound at src/Simplify.hs:31:23) | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty | ^ src/Simplify.hs:31:62: error: [GHC-83865] • Couldn't match expected type ‘Expr’ with actual type ‘t1 a0’ • In the second argument of ‘add’, namely ‘acc’ In the expression: add x acc In the expression: if null acc then x else add x acc • Relevant bindings include acc :: t1 a0 (bound at src/Simplify.hs:31:25) x :: t1 a0 (bound at src/Simplify.hs:31:23) | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty | ^^^ src/Simplify.hs:31:67: error: [GHC-83865] • Couldn't match expected type ‘t1 a0’ with actual type ‘Expr’ • In the second argument of ‘foldr’, namely ‘empty’ In the expression: foldr (\ x acc -> if null acc then x else add x acc) empty In an equation for ‘addAll’: addAll exprs = foldr (\ x acc -> if null acc then x else add x acc) empty where empty = NumLit 3 | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty |

Terminal output

Error: [Cabal-7125] Failed to build Simplify-0.1.0.0 (which is required by exe:mark from Simplify-0.1.0.0 and test:SimplifyTest from Simplify-0.1.0.0). charlotte@Charlotte-DELL:~/functional/CW2-Simplify$ #

At the moment, this question is hard to write a good answer for, because it's unclear how you're stuck. You're much more likely to get good, targeted help if you put in a bit more effort to solve the problem yourself, and give us a glimpse into what's preventing progress for you. Have you read the errors? Do you understand them? If so, what's stopping you from fixing them? If not, what's confusing about them? — Daniel Wagner
– Daniel Wagner, Commented Nov 11 at 18:00
The phrase "without introducing any junk" makes me think you need foldr1, not just foldr. — Louis Wasserman
– Louis Wasserman, Commented Nov 11 at 19:01
This is a case where Haskell's error messages are notoriously hard to read: you are missing the exprs argument to the foldr. — Noughtmare
– Noughtmare, Commented Nov 12 at 13:32

K. A. Buhr · Accepted Answer · 2025-11-12 14:26:58Z

The first error message is saying that for this highlighted expression:

 | 31 | addAll exprs = foldr(\x acc -> if null acc then x else add x acc) empty | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

the compiler expected the type to be Expr but determined the type to have a much different form t0 (t1 a0) -> t1 a0.

The first question you should answer is: does the type the compiler expected match the type you expected. You wanted addAll to take an argument exprs :: [Expr] and return an Expr, so it looks like addAll exprs should have type Expr, so the right hand side of the equals sign should have type Expr. That's a good start: at least you and the compiler agree on what to expect.

Where do we go from here? The other type t0 (t1 a0) -> t1 a0 doesn't seem to be much help, but if you read the error message carefully, there's a hint: Probable cause: 'foldr' is appled to too few arguments. Well, foldr takes three arguments: a function, a "base case" and a list, and you've given it three arguments, right? There's the function, empty is the base case, and there's the... erm... well, the list seems to be missing, doesn't it?

There are two common methods to writing a function that's actually a foldr, you can write out all the arguments:

mySum :: [Int] -> Int mySum numbers = foldr (+) 0 numbers

or you can leave out the common final argument to write it in a sort of "higher level" style:

mySum :: [Int] -> Int mySum = foldr (+) 0

If you try and mix and match these methods as you've done here:

mySum :: [Int] -> Int -- ERROR mySum numbers = foldr (+) 0

you'll get this sort of error message.

Anyway, if you fix up the right-hand side so exprs is supplied to foldr:

addAll exprs = foldr (\x acc -> if null acc then x else add x acc) empty exprs

that should clear up most of those error messages.

You'll have another error message now about the acc in null acc being the wrong type, but that's a completely separate issue, and I think you know why that's an error. You're hoping to detect the first step of the fold when the accumulated expression is still empty by treating acc as a list and checking if it's null, but acc is an Expr, not a list, so that's not going to work. I think the advice you were given to use foldr was bad advice. You should use foldr1, which doesn't need the "empty" argument, or you should forget about foldr/foldr1 entirely, and go back to old style recursion:

addAll [] = error "Can't add an empty list of expressions" addAll [e] = ...something non-recursive... addAll (e:es) = ...something recursive...

Collectives™ on Stack Overflow

Haskell Foldr ADT from a List of Expressions into a single expression

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related