foldr for squareOn - Haskell

Question

In my lecture, we had to define the function squareOn such that

with foldr. The answer was

 squareOn :: (Eq a, Num a) => [a] -> a -> a        
 squareOn = foldr (\x acc y -> if y == x then x*x else acc y) id

I undestand how foldr works, but I'm new at lambda expressions in Haskell. Is acc any type of function from Haskell? It would be nice if someone could explain how squareOn works. :)

`acc` is just a variable name like `x` and `y`. It's short for *accumulator*, and is quire common (idiomatic?) in Haskell — Mark Seemann, Feb 19 '21 at 13:17
`acc` is not *any* type; it is specifically one of type `a -> a`, like `id`. — chepner, Feb 19 '21 at 14:05

score 1 · Accepted Answer · answered Feb 19 '21 at 14:07

This is a sort-of advanced usage of foldr. Normally, we see foldr used as in

fun xs = foldr (\x acc -> something using x and acc) base xs

or equivalently

fun = foldr (\x acc -> something using x and acc) base

which corresponds to the following recursive function:

fun []     = base
fun (x:xs) = something using x and acc
   where acc = fun xs

Your case is a special case of this usage, where base, acc, and something using x and acc are functions. That is, we have

fun []     = \y -> base'
fun (x:xs) = \y -> something using x, acc, y
   where acc = \y -> fun xs y

Moving back to foldr, we get

fun = foldr (\x acc -> \y -> something using x, acc, y) (\y -> base')

which can also be written as

fun = foldr (\x acc y -> something using x, acc, y) (\y -> base')

where a somehow confusing three-argument function appears to be passed to foldr.

Your specific case,

squareOn = foldr (\x acc y -> if y == x then x*x else acc y) id

corresponds to the explicit recursion:

squareOn []     = id
squareOn (x:xs) = \y -> if y == x then x*x else acc y
   where acc = \y -> squareOn xs y

or

squareOn []     y = y
squareOn (x:xs) y = if y == x then x*x else squareOn xs y

which you should be able to understand.

score 0 · Answer 2 · answered Feb 19 '21 at 14:05

Let's define this function without a lambda.

squareOn :: (Eq a, Num a) => [a] -> a -> a
squareOn = foldr f id
  where
    f x acc = g
      where
        g y | x == y = x * x
            | otherwise = acc y

Now it's become what foldr usually looks like. It takes a function taking two arguments f and an initial value id.

When you pass [2, 4] to squareOn, it'll be expanded to foldr f id [2, 4], then f 2 (f 4 id) by the definition of foldr.

f 4 id returns a function that takes one argument y which returns 4 * 4 if y is 4, and returns id y otherwise. Let's call this function p.

p y | 4 == y = 4 * 4
    | otherwise = id y

Now, f 2 (f 4 id) returns a function that takes one argument y which returns 2 * 2 if y is 2, and returns p y otherwise. When you name it q, it'll be like this.

q y | 2 == y = 2 * 2
    | otherwise = p y

So squareOn [2, 4] 3, for example, is equivalent to q 3.

score 0 · Answer 3 · answered Apr 03 '21 at 12:07

Whoever skipped those explicit arguments just made it unnecessarily harder on yourself to learn this stuff. It's totally superficial. Adding the explicit arguments, as specified by the type signature, gives us

squareOn :: (Eq a, Num a) => [a] -> a -> a
squareOn      = foldr (\x acc y -> if y == x then x*x else acc y) id
squareOn xs   = foldr (\x acc y -> if y == x then x*x else acc y) id xs
squareOn xs y = foldr (\x acc y -> if y == x then x*x else acc y) id xs y
squareOn xs y = foldr g id xs y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y }
squareOn xs y = (case xs of { 
    []      -> id ;
    (x:xs2) -> g x (foldr g id xs2)
                          })  y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y }

Now we can see everything in play here, as opposed to having to keep it all in mind. There is playing chess, and then there's playing blindfold chess, and why play it blindfolded if you can just see?

So now it becomes obvious that passing that y around^(*) from call to call unchanged actually has no purpose here, because it is the same y, and it is already in scope:

squareOn xs y = (case xs of { 
    []      -> y  ;
    (x:xs2) -> g x (foldr g y  xs2)
                          })      where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }

which simplifies back as just

squareOn xs y = foldr g y  xs     where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }
{- cf.
squareOn xs y = foldr g id xs y   where { g x acc y | y == x    = x*x 
                                                    | otherwise = acc y } -}

And to be pointlessly short and pointfree, like your original code,

squareOn      = flip (foldr g)    where { g x acc   | y == x    = x*x 
                                                    | otherwise = acc   }

Or it could be simplified to

squareOn xs y =  case xs of { 
    []             -> y   ;
    (x:_) | y == x -> x*x ;
    (_:xs2)        -> squareOn xs2 y }

and further to a worker/wrapper with nested unary worker, whichever is clearer for you.

Passing the unchanged quantity around to have it in scope is only really needed in languages without nested scope, like Prolog.

^(*)_{(so that explanation in full, which you asked for, about how this technique works, is actually in the linked answer).}

foldr for squareOn - Haskell

3 Answers3