haskell - 替换列表中的元素

Question

我需要实现一个替换列表中元素的函数——
要替换的索引是 fst在元组中，snd在元组中
是什么来代替它。我被要求使用 foldr或 map功能。

例如:

setElements   [(1, 'a'), (-4, 't'), (3, 'b')] "#####" = "#a#b#" 

setElements函数无法编译:

我的代码:

setElement :: Int -> a -> [a] -> [a]
setElement n x xs = if ((n < length xs) && n >= 0)
                    then (take n xs) ++ [x] ++ (drop (n + 1) xs)
                    else xs

setElements :: [(Int, a)] -> [a] -> [a]
setElements = foldr (\t l-> setElement (fst t) (snd t) l) [] 

我得到:

• Couldn't match type ‘[a]’ with ‘[a] -> [a]’ 
  Expected type: [(Int, a)] -> [a] -> [a] 
  Actual type: [(Int, a)] -> [a] 
• Possible cause: ‘foldr’ is applied to too many arguments 
  In the expression: foldr (\ t l -> setElement (fst t) (snd t) l) [] 
  In an equation for ‘setElements’: 
      setElements = foldr (\ t l -> setElement (fst t) (snd t) l) [] 
• Relevant bindings include 
    setElements :: [(Int, a)] -> [a] -> [a] 
    (bound at hw3.hs:79:1) 
   | 
79 | setElements = foldr (\t l-> setElement (fst t) (snd t) l) [] 
   |

如何修复错误？

Answer 1

让我们看看你的功能:

setElements :: [(Int, a)] -> [a] -> [a]
setElements = foldr (\t l-> setElement (fst t) (snd t) l) []

并记忆 foldr 的类型:

foldr :: (a -> b -> b) -> b -> [a] -> b

在您使用 foldr , 你有 a如(Int, a)和 b如[a] .你只给它前两个参数。所以foldr (\t l-> setElement (fst t) (snd t) l) []有类型 [(Int, a)] -> [a] - 而setElements应该有类型 [(Int, a)] -> [a] -> [a] .请注意这些如何与 GHC 在错误消息中报告的“实际类型”和“预期类型”完全匹配。

为了解决这个问题，我实际上会后退一步。折叠是正确的想法-您的setElement函数已经根据索引和新值修改了原始列表(它的第三个参数)，您想要的是获取编码此数据的对列表，并继续应用此函数重复更新原始列表。 (当然这是 Haskell，所以数据是不可变的——你并不是在原地更新它，而是每次都简单地返回一个新列表。但有时像这样松散地说更容易。)

这正是折叠的含义。让我们试着把它写出来，不要试图太花哨地使用“无点”方法，而是完全应用它:

setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr myFunction as ps
    where myFunction = undefined

undefined这只是一个占位符 - 如果您尝试使用该函数，它将导致运行时错误(但不会导致编译错误)，我把它放在那里是因为我们需要考虑这一点，折叠函数通常是实现折叠最棘手的部分。但是让我们检查一下我们是否理解其他术语在做什么:我们实际上“走”的列表是 (Int, a) 的列表。告诉我们要插入什么以及在哪里插入的术语 - 这就是我所说的 ps (p 用于“对”)。因为我们从 a 的列表开始s - 我在逻辑上称之为 as这里 - 那么这应该是起始累加器值，它是 foldr 的第二个参数.

所以剩下的就是 fold 函数——它接受一对和一个列表，并根据对中的值更新列表。好吧，这是您已经在使用的功能:

\t l-> setElement (fst t) (snd t) l

或者，用模式匹配重写(我发现它更具可读性，因此我认为这是大多数 Haskell 开发人员的首选):

\(i, a) as -> setElement i a as

因此，将其代入，我们得出以下定义:

setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr myFunction as ps
    where myFunction = \(i, a) as -> setElement i a as

这现在将编译并正常工作。但是当你有一个工作函数时，总是值得退后一步，看看你是否可以简化它的定义。事实上myFunction可以简化很多:

\(i, a) as -> setElement i a as

可以首先被“eta-reduced”到

\(i, a) -> setElement i a

使用标准库函数，它就是 uncurry setElement .

在这个阶段，我们显然不需要 where不再有子句(实际上我们以前从未这样做过，但 imo 它有助于任何不是很简单的 lambda 的可读性)，并且可以只写:

setElements :: [(Int, a)] -> [a] -> [a]
setElements ps as = foldr (uncurry setElement) as ps

事实上，虽然我不一定会推荐它，但如果我们在玩代码高尔夫，你甚至可以更进一步，只写:

setElements = flip . foldr . uncurry $ setElement

我个人认为，能够以简洁的方式表达相对复杂的功能，如上所述，这绝对是 Haskell 魅力的一部分。但是，与其直接尝试写这样的东西，在我看来，最好从一些非常具体的东西开始，展示你想要如何转换你的数据——并且只有在开始工作之后，如果你想寻找更简洁的表示想要。