I am doing an exercise of fp-course: https://github.com/system-f/fp-course/blob/5e0848b4eacb3ddff65553ab5beb6447b73f61b3/src/Course/Applicative.hs#L77
Correct answer is
(<*>) fs as = foldRight (\f bs -> foldRight (\a bs -> f a :. bs) Nil as ++ bs) Nil fs
I trying to take the inner foldRight
into where
sub sentence, an error occurred.
(<*>) fs as = foldRight (\f bs -> f as ++ bs) Nil fs
where f as = foldRight (\a bs -> f a :. bs) Nil as
The error is
src/Course/Applicative.hs:75:53: error:
• Couldn't match type ‘a’ with ‘List a’
Expected: List (List a -> List b)
Actual: List (a -> b)
‘a’ is a rigid type variable bound by
the type signature for:
(<*>) :: forall a b. List (a -> b) -> List a -> List b
at src/Course/Applicative.hs:(70,5)-(72,13)
• In the third argument of ‘foldRight’, namely ‘fs’
In the expression: foldRight (\ f bs -> f as ++ bs) Nil fs
In an equation for ‘<*>’:
(<*>) fs as
= foldRight (\ f bs -> f as ++ bs) Nil fs
where
f as = foldRight (\ a bs -> f a :. bs) Nil as
• Relevant bindings include
as :: List a (bound at src/Course/Applicative.hs:75:12)
fs :: List (a -> b) (bound at src/Course/Applicative.hs:75:9)
(<*>) :: List (a -> b) -> List a -> List b
(bound at src/Course/Applicative.hs:73:3)
|
75 | (<*>) fs as = foldRight (\f bs -> f as ++ bs) Nil fs
| ^^
src/Course/Applicative.hs:76:25: error:
• Couldn't match type ‘t1’ with ‘List t1’
Expected: t1 -> t2
Actual: List t1 -> List t2
‘t1’ is a rigid type variable bound by
the inferred type of f :: t1 -> t2
at src/Course/Applicative.hs:76:25-68
• In an equation for ‘<*>’:
(<*>) fs as
= foldRight (\ f bs -> f as ++ bs) Nil fs
where
f as = foldRight (\ a bs -> f a :. bs) Nil as
In the instance declaration for ‘Applicative List’
• Relevant bindings include
f :: t1 -> t2 (bound at src/Course/Applicative.hs:76:25)
|
76 | where f as = foldRight (\a bs -> f a :. bs) Nil as
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Failed, 10 modules loaded.
How to take inner foldRight
into where
?
If you're binding the name f
to the functions from the input list, it's a pretty bad idea to name your local function also f
! The effect of this is actually that you're not using your function at all, because its definition is shadowed by the lambda binding \f bs -> ...
. Just call it something like innerFold
.
Talking of shadowing, there's no need to make as
an argument to this function because as
is already in scope anyway. It means you'll have two variables called as
which just happen to always have the same value. Don't do this.
You do however need to make f
an argument of this function, because that is only bound in the lambda of the outer fold:
fs<*>as = foldRight (\f bs -> innerFold f ++ bs) Nil fs
where innerFold f = foldRight (\a bs -> f a :. bs) Nil as
Note that the ++ bs
is unnecessary and inefficient here. You only need that because the inner fold always piles its results onto Nil
, but better is to just pile onto the outer bs
straight away, this way you avoid that each chunk needs to be traversed again for appending:
fs<*>as = foldRight (\f bs -> innerFold f bs) Nil fs
where innerFold f bs = foldRight (\a cs -> f a :. cs) bs as
...which can be eta-reduced
fs<*>as = foldRight innerFold Nil fs
where innerFold f bs = foldRight (\a cs -> f a :. cs) bs as
or shorter
fs<*>as = foldRight innerFold Nil fs
where innerFold f bs = foldRight (\a -> (f a :.)) bs as
or even
fs<*>as = foldRight innerFold Nil fs
where innerFold f bs = foldRight ((:.) . f) bs as
(not necessarily recommended.)