如何使用fst函数实现head函数

Question

我承认这是我的作业。但苦思冥想实在找不到好的解决办法。

可能有一些愚蠢的方法可以实现这一点，例如：

myHead (x:[]) = x
myHead (x:y:xs) = fst (x, y)

但我认为这并不是老师想要的。
顺便说一句，不需要错误处理。

提前致谢！

Answer 1

有一个非常自然的函数，它不在前奏中，称为“uncons”，它是未柯里化 cons 的逆函数。

cons :: a -> [a] -> [a]
uncurry cons :: (a, [a]) -> [a]

uncons :: [a] -> (a, [a])
uncons (x:xs) = (x, xs)

您可以使用它来实现 head 为

head = fst . uncons

为什么是uncons自然的？

您可以将列表视为通过使用两个构造函数定义的数据类型

nil :: [a]
nil = []

cons :: (a, [a]) -> [a]
cons (a,as) = a:as

您也可以将其视为由函数解构的数据类型

destruct :: [a] -> Maybe (a, [a])
destruct [] = Nothing
destruct (a:as) = Just (a, as)

要解释为什么这些与列表类型如此明确地联系在一起，远远超出了这个答案，但查看它的一种方法是尝试定义

nil      :: f a
cons     :: (a, f a) -> f a

或者

destruct :: f a -> Maybe (a, f a)

对于任何其他容器类型f。你会发现它们都与列表有着非常密切的关系。

您几乎已经可以uncons在 的定义的第二种情况中看到destruct，但是有一个Just障碍。这与未在空列表中定义的和uncons更好地配对headtail

head [] = error "Prelude.head"

所以我们可以调整之前的答案以适用于无限流。这里我们可以认为无限流是由一个函数构造的

data Stream a = Next a (Stream a)

cons :: (a, Stream a) -> Stream a
cons (a, as) = Next a as

并被一个函数破坏

uncons :: Stream a -> (a, Stream a)
uncons (Next a as) = (a, as)

-- a. k. a.
uncons stream = (head stream, tail stream)

两者互为倒数。

现在我们可以通过获取返回元组的第一个元素来head获取sStreamuncons

head = fst . uncons

这就是head中的模型Prelude，所以我们可以假装列表是无限流并以这种方式定义 head

uncons :: [a] -> (a, [a])
uncons (a:as) = (a, as)

-- a. k. a.
uncons list = (head list, tail list)

head = fst . uncons