为什么我对空列表调用 foldr 的结果顺序不正确？

Question

我正在尝试完成 Haskell 九十九题中的第 8 题，但是我无法理解为什么我的函数的列表结果排序错误。

compress 函数的目的是从输入列表中消除任何重复的字母，并输出另一个包含唯一字母的列表，这些字母按照它们在输入列表中首次出现的顺序排列。这是我的压缩功能代码：

compress l = foldr f [] l where f a b = if a `elem` b then b else a : b

当重复的字母彼此相邻时，它可以正常工作，因此“aaaabbb”输出“ab”，这是正确的，但是当重复的字母被另一个字母分隔时，它会改变输出中的顺序，因此输出“aba” “ba”而预期输出是“ab”。

即使在写出 foldr 的堆栈跟踪时，我似乎也得到了预期的输出，但是当运行 GHCI 中的代码带有“aba”或“abca”等输入时，我得到了不正确的结果.是什么导致了这种行为？为什么当一个重复的字母被不同的字母分隔时，输出的顺序会改变？

Answer 1

foldr 函数以一个初始值（b 类型）和一个 Foldable 容器 t 开始。对于容器中的 'each' a 值，它使用 a 值和 'current' b 值调用函数 (a -> b -> b)。

Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

在compress中，初始值为[]，这也使得编译器能够推断出Foldable实例是[]。

现在尝试 GHCi 中的步骤。定义（仅针对 GHCi 会话）f 作为 top-level 函数：

Prelude> f a b = if a `elem` b then b else a : b

如果输入是"aba"，第一次调用f，b值为[]，a值为'a'，因为 foldr 从右边弃牌。

Prelude> f 'a' []
"a"

return 值 "a" 现在成为下一次的累加器值 b：

Prelude> f 'b' "a"
"ba"

这是因为 f 将 'b' 转换为 "a"。

累加器值现在是 "ba"。再次将它传递给 f，使用列表中的第三个也是最后一个值：

Prelude> f 'a' "ba"
"ba"

参见例如概述了探索和 'debug' Haskell 功能的交互方式。

Answer 2

compress l = foldr f [] l where f a b = if a `elem` b then b else a : b
... "aba" outputs "ba" whereas the expected output is "ab".

foldr 列表非常简单。它被定义为

foldr g z [a,b,c,...,n]  =  g a (foldr g z [b,c,...,n])

-- and by generalization,
foldr g z [          n]  =  g n z

-- which means
foldr g z [           ]  =      z

仅此而已。看起来 self-explanatory，不是吗？只需 re-write 您的 foldr 调用，在句法上，立即 确切地 了解发生了什么。特别是re-writing你的定义有点，我们有

compress xs  =  foldr f [] xs
    where
    f a r  =  if  elem a r  then      r 
                            else  a : r

（我确实（尝试）总是调用组合函数“r”的第二个参数，对于“递归为输入列表的Rest计算Result。）

因此我们有

compress             [a,b,c,...,n]
   =  foldr f []     [a,b,c,...,n]  
   =  f a ( foldr f [] [b,c,...,n] )
   =  if  elem a r  then      r 
                    else  a : r
        where 
        r = foldr f [] [b,c,...,n]
   =  if  elem a r  then      r 
                    else  a : r
        where 
        r = compress   [b,c,...,n]

（使用 where 就好像它是表达式的一部分，就像“翻转的 let”）。也就是说，

compress (x:xs) = if  elem x   r  
                    then       r
                    else   x : r
                  where        r = compress xs
compress []     = []

内容如下：“如果 x 出现在 compressed 其余输入中，跳过它；否则，保留它；然后继续压缩的其余部分”。 _{（所以，称它为 b 是一种误导；表明 a 和 b 是相似的实体；它们是 not -- a（或x）是列表的一个元素，r是其转换后的尾巴).}

所以你知道问题出在哪里了：如果列表中有一个以上的 a，这个定义会保留 last 个，而你想保持第一。

因此，如果连续有多个，则无法观察到这种差异：

       -- 1.                    -- 2.
     a a a a b b b            a a a a b b b
           a     b            a       b

但如果中间有一个字符，那么我们当然可以看到区别：

       -- 1.                    -- 2.
     a a a a b b b a          a a a a b b b a
                 b a          a       b

为什么我对空列表调用 foldr 的结果顺序不正确？

Why is the result of my foldr call on an empty list not in the correct order?

haskell

functional-programming

fold