haskell

Haskell's "where" usage


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?


Solution

  • 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.)