在Haskell中编写以下程序的更好方法

Question

我正在写一个减少自由词的函数.可以将其视为以下算法:

想法是取消列表中的项目,如果它们彼此为负并且彼此相邻.反复应用,直到无法取消.例如[-2,1,-1,2,3] - > [ - 2,2,3] - > [3]

我写了以下代码.它看起来并不优雅.它使用了head,tail多次,并且这个函数的输入共有3个模式,如果它可以减少到2就很好.我想知道是否有更优雅的方法在Haskell中编写它.我怀疑我可以使用折叠,但我不知道如何自然地做到这一点.

freeReduce []  = []
freeReduce [x] = [x]
freeReduce (x:xs)
  | x == -(head xs) = freeReduce (tail xs)
  | otherwise       = if' (rest == [])
                          [x]
                          (if' (x == - (head rest)) (tail rest) (x:rest))
  where rest = freeReduce xs

Answer 1

这是我能做到的最清楚的事情:

freeReduce []       = []
freeReduce (x : xs) = case freeReduce xs of
                           y : ys | y == -x ->     ys
                           ys               -> x : ys

或等效地:

freeReduce = foldr f []
  where f x (y : ys) | y == -x =     ys
        f x ys                 = x : ys

(两者均未经测试.)

看来这freeReduce本质上是严格的.

(我原来的,不正确的尝试:

freeReduce (x : y : rest) | x == -y =     freeReduce rest
freeReduce (x : rest)               = x : freeReduce rest
freeReduce []                       =     []

(未测试).)

Answer 2

您需要访问当前检查点之前和之后的元素,如下所示:

freeReduce :: (Num a) => [a] -> [a]
freeReduce = red []
  where red xs         []           = reverse xs
        red (x:xs) (y:ys) | x == -y = red    xs  ys
        red xs     (y:ys)           = red (y:xs) ys

您将元素从第二个列表移动到第一个列表,并且只比较这些列表的顶部.因此,它是列表中的一个扫描,然后在最后将其反转.

Answer 3

以下代码不足以满足要求吗？

freeReduce[] = []
freeReduce(x:xs) 
  | rest == []         = [x]
  | x == -(head rest)  = (tail rest)
  | otherwise          = (x:rest)
  where rest = freeReduce xs

想法rest总是尽可能地减少,因此唯一的方法就是获得更好的结果,取消x之前rest取消结果rest的尾部rest.

编辑:添加一行来处理空rest.

Answer 4

您可以将它拆分为两个单独的函数,一个只检查列表的前两个元素是否相互抵消,另一个使用它来减少整个列表.

-- check if the first two elements cancel each other
headReduce (x:y:zs) | x == -y = zs
headReduce xs = xs

-- build a whole reduced list from that
freeReduce []     = []
freeReduce (x:xs) = headReduce (x : freeReduce xs)

它的工作原理是因为如果列表完全缩小并且您在前面添加了另一个元素,那么唯一可能的新减少是前两个元素现在相互抵消.然后,每次感应,结果freeReduce总是完全减少.