Haskell中链表的基本操作

Question

我正在尝试为 Haskell 中的链表编写一些基本的列表操作，但我可以用这个手。我想将列表附加到另一个列表，但它根本不起作用，这是我的代码：

data ML a = E | L a (ML a) deriving (Show)
myList = (L 1 (L 2 (L 3 (L 4 E))))
myHead :: ML a -> a
myHead E = error "empty list"
myHead (L a _) = a
myTail :: ML a -> ML a
myTail E = error "empty list"
myTail (L _ a) = a
myAppend :: ML a -> ML a -> ML a
myAppend E a = a
myAppend (x L xs) ys = x L (xs myAppend ys)

我还收到了一个关于如何将此列表显示为"1,2,3"之类的字符串的问题。我得到了一个函数，它显示为这样的列表 [1,2,3] 但不显示为字符串。

toString :: ML a -> [a]
toString E = []
toString (L a l) = a:(toString l)

Answer 1

我认为基本问题在最后一行：

myAppend :: ML a ->ML a ->ML a
myAppend E a = a
myAppend(x L xs)ys =x L (xs myAppend ys)

构造函数是L的，在 Haskell 中，通常将构造函数写在参数之前，例如：

myAppend :: ML a ->ML a ->ML a
myAppend E a = a
myAppend(L x xs)ys =L x (myAppend xs ys)

现在它应该可以工作了。

关于你的第二个问题：toString ML a -> [a].实际上，[a]是一个列表，而不是一个String(好吧，String是Chars：type String = [Char]的列表)，你猜怎么着：Haskell中的列表是一个链表。所以这意味着你的toString :: ML a -> [a]实际上更像是一个toList。

如果你想写一些东西作为String，这意味着元素应该有一个文本表示。您可以使用类型约束(如Show a =>)来编写它。所以现在的签名是：toString :: Show a => ML a -> [String].

我们可以将所有元素 ping 到它们的文本表示map，并将a列表转换为文本表示，例如使用逗号intercalate :: [a] -> [[a]] -> [a]，例如：

import Data.List(intercalate)
toList :: ML a -> [a]
toList E = []
toList (L x xs) = x : toList xs
toString :: Show a => ML a -> String
toString = intercalate "," . map show . toList

或者我们可以"自己实现功能"：

toString :: Show a => ML a -> String
toString E = ""
toString (L x E) = show x
toString (L x xs) = show x++',' : toString xs