haskell - 纯 Haskell Lambda 微积分中列表的仿函数性

Question

我正在尝试使用 Haskell 在纯 lambda 演算中实现各种功能。 一切正常

{-# LANGUAGE RankNTypes #-}

type List a = forall b. (a -> b -> b) -> b -> b

empty :: List a
empty = const id

cons :: a -> List a -> List a
cons x xs f y = f x (xs f y)

直到 List 的 map 出现。

map :: (a -> b) -> List a -> List b
map f xs = xs (cons . f) empty

导致此错误消息:

• Couldn't match type ‘List b’ with ‘(b -> b1 -> b1) -> b1 -> b1’
  Expected type: b
                 -> ((b -> b1 -> b1) -> b1 -> b1) -> (b -> b1 -> b1) -> b1 -> b1
    Actual type: b -> List b -> List b
• In the first argument of ‘(.)’, namely ‘cons’
  In the first argument of ‘xs’, namely ‘(cons . f)’
  In the expression: xs (cons . f) empty
• Relevant bindings include
    f :: a -> b (bound at Basic.hs:12:5)
    map :: (a -> b) -> List a -> List b (bound at Basic.hs:12:1)

为什么 cons 有效而 map 无效？难道 List 的每个实例都适用于 b 的每个值，因为它受 forall 约束吗？

Answer 1

Haskell 的类型系统不够强大，无法像您那样编写 map。改为这样写:

map f xs c n = xs (c . f) n