Haskell的级联和与AList ([a] -> [a])的混淆

Question

我有一个项目，在Haskell，我们正在提高连接列表的速度。我对Haskell很陌生，我对AList (a -> a)感到困惑，特别是如何将自己的AppendedList转换为常规列表。任何帮助都将不胜感激。

newtype AppendedList a = AList ([a] -> [a])

-- List[5] is represented as AList (\x -> 5:x) 
-- This function takes an argument and returns the AppendedList for that 
single :: a -> AppendedList a
single m = AList (\x -> m : x)


-- converts AppendedList to regular List
toList :: AppendedList a -> [a]
toList = ???

Answer 1

最难的部分是不要直接给你答案:)

如果您还记得在Haskell：[1, 2, 3] = 1 : 2 : 3 : []中如何构造列表，那么[]是空列表。

现在，让我们“跟随类型”(我们也将这个思想过程称为TDD，用于类型驱动开发)，看看您手头有什么：

toList :: AppendedList a -> [a]
toList (AList listFunction) = ???

listFunction的类型为[a] -> [a]。因此，您需要为它提供一个多态列表(即的列表，任何类型的)，以便它返回一个列表。

您所知道的的唯一列表是什么类型的？将此列表传递给listFunction，所有内容都会编译，这是一个很好的指示，表明它可能是正确的:D

我希望这在不提供简单答案的情况下有所帮助(目标是让你学习！)

Answer 2

AppendedList a是一种类型。

AList f是这种类型的数据，它有一些函数f :: [a] -> [a]“在其中”。

f是一个从列表到具有相同类型元素的列表的函数。

我们可以使用some_list :: [a]调用它以获得resulting_list :: [a]：

f           :: [a] -> [a]
  some_list :: [a]
-------------------------
f some_list ::        [a]

resulting_list ::     [a]
resulting_list = f some_list 

我们也可以使用resulting_list作为some_list，即..。

resulting_list = f resulting_list

因为它具有相同的类型，这符合f的期望(也因为哈斯克尔的懒惰)。

toList (...) = let { ... = ... } 
               in ...

是一个可能的定义。有了它，

take 2 (toList (single 5))

会返回[5,5]。

编辑:当然，[5,5]不是包含单个5的列表。而且，take 4 ...将返回[5,5,5,5]，因此我们的表示包含任意数量的5，而不仅仅是其中的一个。但是，它只包含一个不同的数字，5。

这让人想起列表的两个应用函式实例，即[]和ZipList。pure 5 :: [] Int确实只包含一个5，但pure 5 :: ZipList Int包含任意数量的5，但只有5。当然，它很难附加无限的列表，所以这主要是一个好奇心。一种思考的食物。

在任何情况下，它都表明有不止一种方法来编写代码，在这里键入代码。这里有不止一张清单可供我们使用。最简单的是[]，但另一个是.我们的名单本身！