How does `until` work?

Question

I wanted to answer to this question using until. But that does not work and I've concluded that I don't understand until.

So I take the function given by the OP, verbatim:

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

Then I write a True/False function retuning whether there is a duplicate:

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

Finally I use until as follows:

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

And that does not work :

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

I misunderstand until, or I did a mistake ?

Answer 1

The until :: (a -> Bool) -> (a -> a) -> a -> a is documented as:

until p f yields the result of applying f until p holds.

It is implemented like:

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

So you provide a predicate p, and a function f. The function is also given an initial value x. By using recursion, it first checks if p x holds. In case it does, it returns x, otherwise, it makes a recursive call with f x as the new x.

So a more clean (but less efficient) implementation is probably:

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

If we analyze your function, we see:

f x = until hasAdjDups removeAdjDups x

So that means f will terminale removing adjacent duplicate characters from the moment it has adjacent duplicate characters. You probably want the opposite predicate:

f x = until (not . hasAdjDups) removeAdjDups x

Or even shorter:

f = until (not . hasAdjDups) removeAdjDups