CODEWITHSUNDEEP
haskellfunction-composition
Johnny
Johnny

Reputation: 447

About Function composition order of execution in Haskell

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.

Upvotes: 1

Views: 200

Answers (2)

Markus Mayr
Markus Mayr

Reputation: 4118

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

Upvotes: 2

chi
chi

Reputation: 116139

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.

Upvotes: 0

Related Questions