1

尝试用新元素替换列表中给定点的元素，然后返回该元素。

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:(y:yl)) z
   | x == (length yf) = (yf:(z:yl))

导致此错误：

Inferred type is not general enough
Expression    : setelt
Expected type : Int -> [a] -> a -> [a]
Inferred type : Int -> [[a]] -> [a] -> [[a]]

似乎没有串联的问题，yf:y:yl所以不知道如何解决。

4

3 回答 3

8

您似乎误解了列表构造函数的(:)作用。Haskell 列表是以(:)空列表结尾的构造函数序列[]，模式匹配只是以相同的顺序反汇编这些构造函数。

因此，当您对真正匹配的内容进行模式匹配时(yf:(y:yl))，您真正匹配的是一个至少包含两个元素的列表，yf并且y, 和yl作为列表的其余部分。

推断的类型不是您所期望的，因为这length yf意味着yf——输入列表的第一个元素——本身就是一个列表。

相反，您需要做的是递归地遍历列表，x当您到达正确的位置时，使用输入的当前元素或替换元素构建一个新列表。一般形式应该类似于标准库函数map，其实现方式如下：

map _ [] = []
map f (x:xs) = f x : map f xs

除了您需要一种方法来跟踪您正在搜索的索引，而不是转换每个元素。

如果应用于 0 或 1 个元素的列表，您当前的函数也会失败，但在更正整个算法后应该很容易修复该问题。

于 2013-04-18T17:34:20.570 回答
0

阅读 CA McCann 的答案以获得更多见解，特别是对于列表太短的问题。在不修改算法的情况下，您可以通过以下简单更改来修复代码：

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:(y:yl)) z
   | x == (length (y:yl)) = (yf:(z:yl))

可以简洁地重写：

 setelt :: Int -> [a] -> a -> [a]
 setelt x (yf:ys@(_:yl)) z
   | x == (length ys) = (yf:(z:yl))
于 2013-04-18T20:07:53.313 回答
0

除了模式匹配的问题（我也推荐 CA McCann 的答案），您的程序可能没有您预期的效率，而且肯定比它可能的效率低。

问题在于 Haskell 的列表是简单的单链表，它们不能以方便的、O(1) 可访问的形式来携带它们的长度。Haskelllength必须计算列表节点的数量，这需要 O(N) 时间。这意味着setelt （由 Nicolas Dudebout 的回答提供）的直接更正版本将在每个 step扫描剩余列表，产生 O(N^2) 最坏情况下的性能，而不是可能的 O(N)。

要解决此问题，请先扫描列表以获取长度。类似于以下实现，它是 O(N) （尽管使用take并drop最终扫描列表的次数超过了严格必要的次数）：

setelt :: Int -> [a] -> a -> [a]
setelt n ys z = front ++ z:back where
  count = length ys - n
  front = take count ys
  (_:back) = drop count ys

最后，如果不清楚：标准的 Haskell 列表索引（由take、drop和使用!!）从列表头部的 0 开始，而不是尾部的 1 （这可能是您对 , 的意图setelt，并且已实现以上）。如果您的意图是从 0 开头，则实现更容易：

setelt n ys z = front ++ z:back where
    front = take n ys
    (_:back) = drop n ys

或者，更有效地：

setelt 0 (y:ys) z = z:ys
setelt n (y:ys) z = y:setelt (n-1) ys z
于 2013-04-18T21:05:25.163 回答