Haskell

Question

我正在尝试通过解决一些在线问题和训练练习来学习haskell。

现在我正在尝试创建一个函数，从列表中删除相邻的重复项。

Sample Input

"acvvca"

"1456776541"

"abbac"

"aabaabckllm"

Expected Output

""

""

"c"

"ckm"

我的第一个想法是创建一个函数，它可以简单地删除相邻重复项的第一个实例并恢复列表。

module Test where

removeAdjDups :: (Eq a) => [a] -> [a]
removeAdjDups []           =  []
removeAdjDups [x]          =  [x]
removeAdjDups (x : y : ys)
  | x == y = removeAdjDups ys
  | otherwise = x : removeAdjDups (y : ys)

*Test> removeAdjDups "1233213443"
"122133"

此函数适用于首次找到的对。

所以现在我需要对函数的结果应用相同的函数。

我认为 foldl 可以提供一些帮助，但我不知道我将如何实现它。

类似于

removeAdjDups' xs = foldl (\acc x -> removeAdjDups x acc) xs

此外，这种方法是实施解决方案的最佳方式还是我应该考虑更好的方式？

Answer 1

从last-first顺序开始：首先从尾部删除重复项，然后检查输入的头部是否等于尾部结果的头部（此时，不会有任何重复项，所以唯一可能的对是输入的头部与尾部结果的头部）：

main = mapM_ (print . squeeze) ["acvvca", "1456776541", "abbac", "aabaabckllm"]

squeeze :: Eq a => [a] -> [a]
squeeze (x:xs) = let ys = squeeze xs in case ys of
                                            (y:ys') | x == y -> ys'
                                            _ -> x:ys
squeeze _ = []

产出

""
""
"c"
"ckm"

Answer 2

我看不出 foldl 有什么用。（通常，foldl 几乎结合了 foldr 和 foldl' 的缺点......这些，或 foldMap，是你通常应该使用的折叠，而不是 foldl.)

您的意图似乎是：重复 removeAdjDups，直到再也找不到重复项。重复是

的工作

iterate :: (a -> a) -> a -> [a]

喜欢

Prelude> iterate removeAdjDups "1233213443"
["1233213443","122133","11","","","","","","","","","","","","","","","","","","","","","","","","","","",""...

这是一个不断减少的无限列表。一般会不会收敛到空表；你会想要添加一些终止条件。如果你想根据需要删除尽可能多的重复项，那就是 fixpoint;它可以以与您实现 removeAdjDups 的方式非常相似的方式找到：比较相邻元素，只是这次在 reductions.

列表中

处理递归重复要好得多，它避免了不必要的比较和遍历列表的开头。

Answer 3

列表理解经常被忽视。它们当然是语法糖，但像我这样的一些人会上瘾。首先，字符串本身就是列表。这个函数可以处理任何列表，也可以处理单例和空列表。您可以使用 map 来处理一个列表中的多个列表。

(\l -> [ x  | (x,y) <- zip l $ (tail l) ++ " ", x /= y]) "abcddeeffa"

"abcdefa"

Answer 4

我也不知道如何使用 foldl。可能是因为，如果你想在这里折叠东西，你必须使用foldr。

main = mapM_ (print . squeeze) ["acvvca", "1456776541", "abbac", "aabaabckllm"]

-- I like the name in @bipll answer
squeeze = foldr (\ x xs -> if xs /= "" && x == head(xs) then tail(xs) else x:xs) ""

我们来分析一下。这个想法来自@bipll 回答：从右到左。如果 f 是 lambda 函数，那么根据 foldr 的定义：

squeeze "abbac" = f('a' f('b' f('b' f('a' f('c' "")))

根据 f 的定义，f('c' "") = 'c':"" = "c" 自 xs == ""。从右边开始的下一个字符：f('a' "c") = 'a':"c" = "ac" 自 'a' != head("c") = 'c'。 f('b' "ac") = "bac" 同理。但是 f('b' "bac") = tail("bac") = "ac" 因为 'b' == head("bac")。等等...

奖励：将foldr替换为scanr，你可以看到整个过程：

Prelude> squeeze' = scanr (\ x xs -> if xs /= "" && x == head(xs) then tail(xs) else x:xs) ""
Prelude> zip "abbac" (squeeze' "abbac")
[('a',"c"),('b',"ac"),('b',"bac"),('a',"ac"),('c',"c")]

Haskell - 从列表中删除相邻的重复项

Haskell - Removing adjacent duplicates from a list

recursion

list

fold