"直到"如何运作？

Question

我想回答这个问题使用until.但这不起作用,我得出的结论是我不理解until.

所以我采用OP给出的功能,逐字:

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

然后我写一个True/False函数重新调整是否有重复:

hasAdjDups :: (Eq a) => [a] -> Bool
hasAdjDups []           =  False
hasAdjDups [x]          =  False
hasAdjDups (x : y : ys)
  | x == y = True
  | otherwise = hasAdjDups (y : ys)

最后我使用until如下:

f :: (Eq a) => [a] -> [a]
f x = until hasAdjDups removeAdjDups x

这不起作用:

> hasAdjDups  "aabccddcceef"
True
> removeAdjDups   "aabccddcceef"
"bf"
> f "aabccddcceef"
"aabccddcceef"

我误解了until,或者我犯了错误？

Answer 1

该until :: (a -> Bool) -> (a -> a) -> a -> a记录为:

until p f得到的结果施加f到p保持.

它实现如下:

until p f = go
  where
    go x | p x          = x
         | otherwise    = go (f x)

所以你提供了一个谓词p和一个函数f.该函数也给出了初始值x.通过使用递归,它首先检查是否p x保持.如果确实如此,则返回x,否则,它将f x以新的方式进行递归调用x.

因此,更干净(但效率更低)的实现可能是:

until p f x | p x = x
            | otherwise = until p f (f x)

如果我们分析您的功能,我们会看到:

f x = until hasAdjDups removeAdjDups x

因此,这意味着f将terminale从它的那一刻去除相邻重复字符具有相邻的重复字符.你可能想要相反的谓词:

f x = until (not . hasAdjDups) removeAdjDups x

甚至更短:

f = until (not . hasAdjDups) removeAdjDups