Haskell fp-course练习：如何将foldRight移至where子句？

我正在完成fp-course的函数式编程练习，List类型的<*>操作正确实现如下：

(<*>) fs as = foldRight (\f bs -> foldRight (\a bs -> f a :. bs) Nil as ++ bs) Nil fs

我尝试把内部的foldRight提取到where子句中，写出了如下代码，但出现错误：

(<*>) fs as = foldRight (\f bs -> f as ++ bs) Nil fs
                where f as = foldRight (\a bs -> f a :. bs) Nil as

报错信息如下：

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.

问题原因 #

核心问题是名字冲突：where子句里定义的f和外层lambda参数的f重名了。外层的f是fs中的元素，类型为a -> b；但你在where子句中将f定义为接收List a返回List b的函数，这导致类型匹配失败——外层lambda调用f as时，Haskell会优先绑定外层的f（类型a -> b），而非where子句中的函数，自然触发类型不匹配错误。

正确提取方式 #

给where子句中的函数换个不冲突的名字，比如applyF：

(<*>) fs as = foldRight (\f bs -> applyF f ++ bs) Nil fs
              where applyF f = foldRight (\a bs -> f a :. bs) Nil as

如果想让函数更通用，也可以把列表参数传入：

(<*>) fs as = foldRight (\f bs -> applyToAll f as ++ bs) Nil fs
              where applyToAll f xs = foldRight (\x ys -> f x :. ys) Nil xs

这样既完成了代码提取，又避免了名字冲突，类型也能正确匹配。

内容的提问来源于stack exchange，提问作者zichao liu