Function evaluation result

Question

Im trying to evaluate manually fc [f1, f2] (\x -> 2) 3 but I don't realize how to match the three parameters: [f1, f2], (\x -> 2) and 3 with the function definition, any help?

The function definition:

fc xss = \f -> let ope x y = x . f . y in foldr1 ope xss

f1, f2 :: Int -> Bool
f1 x = (x `mod` 3) == 0
f2 x = (x `mod` 5) == 0

Thanks,
Sebastián.

Answer 1

Well, first do some η-expansion

fc :: [a->b] -> (b->a) -> a->b
fc xss f = let ope x y = x . f . y in \q -> foldr1 ope xss q
 fc xss f q = let ope x y = x . f . y in foldr1 ope xss q

Then perhaps inline the let

 fc xss f q = foldr1 (\x y -> x . f . y) xss q

You can write [f1, f2] as (==0).(`mod`3) : (==0).(`mod`5) : [].

Now it should be easy enough, remembering that a right-fold simply replaces all : with the fold function.

Answer 2

Remember, all functions in Haskell are functions of a single argument to a single result.

Expressions like func arg1 arg2 arg3 might look like a function applied to 3 arguments, but it's really ((func arg1) arg2) arg3), where func arg1 results in a new function, which is applied to arg2 to get a 3rd function, which is finally applied to arg3.

Definitions like func arg1 arg2 arg3 = ... are syntactic sugar for equivalent definitions like func arg1 = \arg2 -> (\arg3 -> ... ), where we've explicitly written out the intermediate functions produced along the way.

So fc [f1, f2] (\x -> 2) 3 is applying fc to [f1, f2], and then applying the result of that. It's clear how to apply fc to one argument (because it's definition has a single argument), so lets just do the first step and see what we get.

fc [f1, f2] = \f -> let ope x y = x . f . y in foldr1 ope [f1, f2]

That's given us a lambda function, which is something that can be applied. Substituting that into the original expression gives us:

(\f -> let ope x y = x . f . y in foldr1 ope [f1, f2]) (\x -> 2) 3

Now again we've got a function (\f -> ...) applied to one argument (\x -> 2). The result of that is applied again (to 3), but we'll worry about that later.

(\f -> let ope x y = x . f . y in foldr1 ope [f1, f2]) (\x -> 2)
  = let ope x y = x . (\x -> 2) . y in foldr1 ope [f1, f2]

So that's given us the expression foldr1 ope [f1, f2], with the auxilliary definition ope from the let; we could substitute that if we want, but I'll let the name ope stay as a stand in. Substituting that back in (remembering that we've defined ope):

(foldr1 ope [f1, f2]) 3

foldr is equivalent to the following:

foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)

So we can expand the foldr1 expression, remembering that [f1, f2] is the just another way of writing f1:[f2]:

foldr1 ope (f1:[f2]) = ope f1 (foldr1 ope [f2])
                     = ope f1 f2

Substituting that back in gives us:

ope f1 f2 3

Now lets make use of the definition for ope we set aside: ope x y = x . (\x -> 2) . y (again, we could have substituted this in earlier but it just would've meant copying out the definition everywhere we wrote ope above). Remembering that ope is really a function of a single argument, even though we were allowed to define it looking like it has two arguments for convenience, lets apply it one argument at a time:

ope f1 = \y -> f1 . (\x -> 2) . y

So we now have:

(\y -> f1 . (\x -> 2) . y) f2 3

Applying the lambda gives us:

(f1 . (\x -> 2) . f2) 3

And finally we've found that the 3 is an argument to the composition "pipeline" f1 . (\x -> 2) . f2. I'll stop here, but you could use the definition of . to expand this further and find out what ultimate function 3 is being passed to.

So the 3 values [f1, f2], (\x -> 2), and 3 from your original expression didn't need to be matched directly to the arguments defined for fc, because they weren't all arguments to it at all. [f1, f2] was the argument to fc, (\x -> 2) was an argument that was trivially computed by fc [f1, f2] (so you could think of it as a "second argument" to fc if you want; it would be very easy to rewrite the equation for fc so that it appears directly as an argument). 3 on the other hand, was not an argument to a function that's anything close to written directly in the source, it ended up being passed to a function that was computed by the expression fc [f1, f2] (\x -> 2).