About Function composition order of execution in Haskell

Question

I have some trouble understanding this example:

data Row = R [Int]
    deriving Show
data Matrix = M [Row]
    deriving Show

check :: Matrix -> Int -> Bool
check (M matrix) n = foldr ((&&) . (\(R row) -> length row == n)) True matrix


test1 = check (M[R[1,2,3], R[4,5], R[2,3,6,8], R[8,5,3]]) 3 == False

I have this datatype named Row that contains a list of integers, and the Matrix datatype containing a list of rows. I have to check through my function if all rows have the length equal to the second parameter, n. I do not really understand why that foldr works. Let's look at test1. It starts by doing ((&&) . (lambda)) R[8, 5, 3] True Isn't now, some sort of (f.g) x y which is f (g x y) ? If it is so, the result will be &&(lambda R[8, 5, 3] True) <-> && (True True), and Isn't the expresion in the paranthese evaluated first (True True) and it should give me an error ? Please make me understand what the order of execution is and where am I wrong.

Markus Mayr · Accepted Answer · 2022-01-16 17:19:09Z

2

First of all, let us remember what foldr does: It takes a function f, a list xn = [x1, x2, ..., xn] and a starting value s and generates the expression

f x1 (f x2 (... (f xn s) ...))

or equivalently

f x1 $ f x2 $ ... $ f xn $ s

The function composition (.) first applies the right-hand side function and then the left-hand side function, so first your lambda expression, that we call checkRow for now and then (&&). This results in

(&&) (checkRow x1) $ (&&) (checkRow x2) $ ... $ (&&) (checkRow xn) $ True

when inserting True as your starting value.

This can be rewritten in infix notation as

(checkRow x1) && (checkRow x2) && ... (checkRow xn) && True

Edit: Regarding how function composition works in this case, please take a look at the types:

(.) :: (b -> c) -> (a -> b) -> a -> c

Keep in mind that (&&) can be seen as an unary function that returns another (in this case unary) function and follow the types:

(Bool -> (Bool -> Bool)) -> (Row -> Bool) -> Row -> Bool -> Bool

(&&) . checkRow :: Row -> Bool -> Bool

So the composition of (&&) and checkRow is a function that takes a Row and a Bool and returns a Bool. So the right-hand side function is applied to the first input argument and the result is forwarded as the first input argument of the second function. The second function, however, can take multiple arguments.

This lines up nicely with the type of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

or in your case

(Row -> Bool -> Bool) -> Bool -> [Row] -> Bool

edited Jan 16, 2022 at 17:19

answered Jan 16, 2022 at 13:56

Markus Mayr

4,1081 gold badge23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Johnny Over a year ago

So is it safe to generally assume that generally, (f . g) x y, is, mathematically speaking, f (g(x), y)?

chi Over a year ago

@Johnny Yes. In Haskell notation, we have (f.g) x equal to f (g x), hence (f.g) x y is equal to f (g x) y ( not f (g x y)). Note how y is passed to f, not g!

Johnny Over a year ago

(f.g) x y = (f.g x) y = f(g(x)) y = f g(x) y, in the meantime I was writting a simple proof, it is pretty much the same, thanks

chi Over a year ago

@Johnny What you wrote is correct, but note that in Haskell those expressions are parsed differently from what you intended. In Haskell, f.g x means f . (g x), and f g(x) y means f g x y, i.e. (((f g) x) y).

chi · Accepted Answer · 2022-01-16 14:03:37Z

Your issue seems to be related to understanding what the function used in the fold actually does:

(&&) . (\(R row) -> length row == n)

Indeed, it is a bit cryptic. Let's try to rewrite it in an equivalent form. By definition of composition, a.b means \x -> a (b x), hence we get

\x -> (&&) ( (\(R row) -> length row == n) x )

This still looks weird, since we'd like && to be applied to two arguments. We can eta-expand: f is equivalent to \y -> f y. We get

\x -> \y -> (&&) ( (\(R row) -> length row == n) x ) y

which means

\x y ->  ( (\(R row) -> length row == n) x ) && y

Note the types: here x :: Row, while y :: Bool. We can equivalently rewrite the above as

\(R row) y ->  length row == n && y

This means that the fold

foldr ((&&) . (\(R row) -> length row == n)) True [Row r1, Row r2, ...]

simplifies to

length r1 == n && (length r2 == n && ... (... && True))

which amounts to checking that all rows have the same length n.

Collectives™ on Stack Overflow

About Function composition order of execution in Haskell

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related