Haskell

Question

我已经实现了一个函数 (!!=)，它给出了一个列表和一个包含列表中的索引和一个元组的元组新值，用给定的新值更新给定的列表指数.

(!!=) :: [a] -> (Int,a) -> [a]
(!!=) xs (0, a) = a : tail xs
(!!=) [] (i, a) = error "Index not in the list"
(!!=) (x:xs) (i, a) = x : xs !!= (i-1, a)

作为折叠概念的初学者，我想知道是否有一种方法可以使用 foldl 或 foldr 来实现相同的结果？

非常感谢。

Answer 1

我给你一个foldl我认为比较容易理解的版本，也是我能想到的最简单/最直接的版本。

但请注意，您不应该使用 foldl（使用 foldl': https://wiki.haskell.org/Foldr_Foldl_Foldl'）- 也不应该像这样使用 ++（使用 : 和反转之后) ;)

总之就是这个想法：

(!!=) xs (i, a) = snd $ foldl 
   (\(j, ys) x -> (j+1, if j == i then ys ++ [a] else ys ++ [x])) 
   (0, []) 
   xs

作为折叠的 state/accumulator 我采用当前索引和累积结果列表的元组（因此 snd 因为我只想要这到底）
然后折叠函数只需要查看我们是否在索引处并交换元素 - 返回下一个索引和新的累积列表

作为练习，您可以尝试：

使用 : 代替 ++ 和 reverse
重写为foldr
查看 zipWith 并使用此 (zipWith (...) [0..] xs) 而不是 fold 重写（这类似于使用地图与索引

Answer 2

foldl 和 foldr 都不能高效地完成这项工作（除非你在折叠时通过列表上的模式匹配来“作弊” ), 尽管 foldr 可以做得不那么糟糕。不，您真正需要的是一种不同风格的折叠，有时称为 para:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para _f n [] = n
para f n (a : as) = f a as (para f n as)

para 与 foldr 非常相似。它们中的每一个都接受一个组合函数，并且对于每个元素，传递该元素的组合函数以及折叠列表其余部分的结果。但是 para 增加了一些额外的东西：它也传递了列表的其余部分！因此，一旦到达替换点，就无需重建列表的尾部。

但是...你如何从头数 foldr 或 para？这就引入了一个经典技巧，有时称为“高阶弃牌”。它不是 para go stop xs 生成 list，而是生成一个 function，它将插入位置作为参数。

(!!=) :: [a] -> (Int, a) -> [a]
xs0 !!= (i0, new) = para go stop xs0 i0
  where
    -- If the list is empty, then no matter what index
    -- you seek, it's not there.
    stop = \_ -> error "Index not in the list"

    -- We produce a function that takes an index. If the
    -- index is 0, we combine the new element with "the rest of the list".
    -- Otherwise we apply the function we get from folding up the rest of
    -- the list to the predecessor of the index, and tack on the current
    -- element.
    go x xs r = \i -> case i of
      0 -> new : xs
      _ -> x : r (i - 1)

请注意 para 很容易实现 foldr:

foldr c = para (\a _ b -> c a b)

可能不太明显的是 foldr 可以实现一个（非常低效的版本）para:

para f n = snd . foldr go ([], n)
  where
    go x ~(xs, r) = (x : xs, f x xs r)

以免您产生错误的想法并认为 para“优于”foldr，知道当它的额外功能 不需要时 , foldr 更易于使用，并且通常会被编译为更高效的代码。

Haskell - 使用 foldl 或 foldr 而不是模式匹配来使用给定索引处的新值更新列表

Haskell - using foldl or foldr instead of pattern matching for updating a list with a new value at a given index

functional-programming

list

pattern-matching

fold