字符串上的Foldl

Question

我想折叠一个字符串，使得在@之前出现的0被替换为"k"。因此，"a.@0.1.2.0" 变成了 "a.@k.1.2.0"。我该怎么做？到目前为止，我的尝试是：

test = foldl(\x acc-> if((last acc) == "@" && x == "0" then acc ++ "k" else acc ++ x)) "" "a.@0.1.2.0"

然而，它并没有生效。Foldl 期望的是字符串列表，但我提供的只是一个字符串。我该如何克服这个问题？

- Andrew

---

不要使用 foldl 来解决这个问题。这明显是一个 foldr 或者 mapAccumL 的问题。使用 foldl 会使得程序变慢。 - dfeuer

但是如果我使用foldr，我如何知道给定的0是否在@之前？ - Andrew

为什么要使用任何折叠呢？ - melpomene

是的，mapAccumL 对于列表来说就是一个折叠函数，可能是最简单的方法了。foldr 也可以实现，但有点棘手。 - dfeuer

我会使用显式递归和模式匹配。你真的需要使用折叠吗？ - chi

Answer 1

采纳Chi的建议：

rep "" = ""
rep ('@' : '0' : xs) = "@k" ++ rep xs
rep (x : xs) = x : rep xs

如果我们想要更加高级一些，

rep = snd . mapAccumL go False
  where
    go True '0' = (False, 'k')
    go _ '@' = (True, '@')
    go _ x = (False, x)

甚至更多

rep = snd . mapAccumL go 'x'
  where
    go '@' '0' = ('0', 'k')
    go _ y = (y, y)

使用foldr与第二种方法（只是因为它更短；第一种方法也可以正常工作，并且允许泛化）：

rep xs = foldr go (const "") xs 'x'
  where
    go '0' r '@' = 'k' : r '0'
    go x r _ = x : r x

要使用 zipWith（更难以泛化）：

rep xs = zipWith go ('x' : xs) xs where
  go '@' '0' = 'k'
  go _ x = x

- dfeuer

Answer 2

正如其他人评论的那样，`foldl` 不适合这项任务。然而，使用差分列表的思想，您仍然可以使用 `foldl` 以有效的方式完成这个任务。

repl :: String -> String
repl a = foldl loop id a ""
    where
    loop :: (String -> String) -> Char -> (String -> String)
    loop f '@' ('0':rest) = f ('@':'k':rest)
    loop f x xs = f (x:xs)

仅出于演示目的以及问题要求使用 foldl 解决方案（不过我并不推荐用这种方式）。

- behzad.nouri

---

虽然这应该具有正确的渐近边界，就像“反向构建，然后反转”技术一样，但它在列表的脊柱上是完全严格的，因此在实践中效率低下。 - dfeuer