list - 如何使用自定义版本的List : `data List a = Nil | Cons a (List a)` ?

Question

此问题基于 Graham Hutton 所著的《Programming in Haskell》一书第二版中的“Declaring Types and Classes”一章中的示例。

数据声明为: 数据列表 a = Nil |缺点(列表a)

使用此声明的示例函数是:

len :: List a -> Int
len Nil = 0
len (Cons _ xs) = 1 + len xs

但无论我尝试什么，我似乎都无法使用函数len:

• len 缺点 1 缺点 2 缺点 3
• 长度1
• len 缺点
• 长度 (1)
• 长度[1,2]
• len 缺点 [1]
• len (1,2)
• len 缺点 (1,2)
• len 缺点 1 2
• len(缺点(1,2))
• len(缺点 1 2)

我是否错过了 len 和 Cons 的任何排列？或者这个例子根本行不通？

Answer 1

您传递给 len 的参数不是 List。列表末尾有 Nil，因此列表的形式为 Nil、Cons … Nil、Cons … (Cons … Nil )、Cons … (Cons … (Cons … Nil)) 等。因此最终对于每个列表，列表的末尾都会标记为 Nil。 Nil 相当于 Haskell 的 [a] 类型的 []。

此外，例如，您不能传递 len Cons 1 Nil，因为这样它将被解释为 ((len Cons) 1) Nil。该参数应该是一个列表。通过使用括号，您可以将其写为 len (Cons 1 Nil)。

对于给定的示例数据，您可以将其重写为:

• len Cons 1 Cons 2 Cons 3 → len (Cons 1 (Cons 2 (Cons 3 Nil)))
• len 1 → len(缺点 1 无)
• len 缺点 → len Nil
• len (1) → len(缺点 1 无)
• len [1,2] → len(缺点 1(缺点 2 无))
• len 缺点 [1] → len(缺点 1 无)
• len (1,2) → len(缺点 1(缺点 2 无))
• len Cons (1,2) → len (Cons 1 (Cons 2 Nil))
• len Cons 1 2 → len (Cons 1 (Cons 2 Nil))
• len(缺点(1,2)) → len(缺点 1(缺点 2 无))
• len(缺点 1 2) → len(缺点 1(缺点 2 无))

您还可以使用OverloadedLists [haskell-doc]扩展以使用列表语法代替。在这种情况下，您需要实现 IsList类型类别:

{-# LANGUAGE <b>TypeFamilies</b> #-}

import GHC.Exts(IsList(..))

data List a = Nil | Cons a (List a)

instance <b>IsList (List a)</b> where
    type Item (List a) = a
    toList Nil = []
    toList (Cons x xs) = x : toList xs
    fromList [] = Nil
    fromList (x:xs) = Cons x (fromList xs)

如果您随后启用 OverloadedLists 扩展，则可以将它们写为列表文字:

{-# LANGUAGE <b>OverloadedLists</b> #-}

-- …

main = print (len <b>[1,2]</b>)