时间戳

首页 > 解决方案 > Haskell 中的正确前缀函数

haskell - Haskell 中的正确前缀函数

问题描述

我想创建一个打印列表前缀的 Haskell 函数：

该函数应执行以下操作：

> prefixes "123"
["","1","12"]
> prefixes "1"
[""]

我写了以下代码：

prefixes :: [a] -> [[a]]
prefixes [] = []:[]
prefixes f =  f : prefixes(init(f))

该函数将输入的字符串或字符打印为前缀，并以相反的方向打印。我想删除它，所以当我输入“123”时，它应该如上打印并以正确的方向显示。

我们可以用：

reverse (drop 1 f)

命令，但我不知道如何在我的函数中实现它。

你能帮我解决这个问题，让它正确打印吗？

标签： haskell

解决方案

您的基本情况不正确，空列表没有适当的前缀。很明显，在基本情况下，您必须返回空列表才能使函数正确。

现在考虑递归情况。一方面，它应该总是以空列表开头（因为的前缀(x:xs)总是[[],...]）。我们如何构造列表的其余部分（的非空前缀(x:xs)？

我们想使用递归，那么我们如何从 的正确前缀集合中构建非空正确前缀(x:xs)的集合xs？看你的例子"123"，"23"are["", "2"]的前缀，我们要构造的非空前缀是["1","12"]，所以我们只是添加'1'到尾部的每个前缀的头部。

所以在递归的情况下：空列表是一个适当的前缀，并且列表的头部添加到尾部的任何适当的前缀。

这是一段代码，可以满足您的要求：

prefixes []     = []
prefixes (x:xs) = [] : map (x:) (prefixes xs)

推荐阅读