Taking change - convergent iteration through iterate

Question

For the Code Review community challenge "Implement StackSTV", the algorithm requires a "convergent iterative scheme" to calculate the keep ratios of candidates that have been elected.

To simplify the calculation of those keep ratios I have written following function to truncate an infinite list that calculates the keep ratio scheme's next step.

I wonder whether I missed some basic library function and whether the function is idiomatic haskell:

{-
 Take items from a list, as long as the last item taken is not the same as the next item in the list.
 Passing an empty list returns an empty list.
-}
takeModified :: Eq a => [a] -> [a]
takeModified (x:xs) = [x] ++ go x xs
 where
 go :: Eq a => a -> [a] -> [a]
 go elem (x':xs')
 | elem == x' = []
 | otherwise = [x'] ++ go x' xs'
 go elem [] = []
takeModified [] = []

• Gurkenglas: Here's a oneliner: map head . takeWhile (null . drop 1) . group
• Zeta: @Gurkenglas not the same behaviour. takeModified $ repeat 0 will lead to [0], whereas your code leads to [].
• Gurkenglas: Oh, you're right, I never include the first duplicate.

Answer 1

• Typically, where clauses don't include full type annotations, though this is mostly a matter of personal preference.
• For prepending items to a list, prefer x:xs over [x] ++ xs.
• In your "base case" of the recursive go function: go elem [] = [], elem is not used. Prefer _ in this case.
• Your comment exceeds 80 characters in width. Again, a matter of personal preference. The note about passing an empty list returns an empty list is probably not necessary as this is very clearly the case from the code itself.

Here is how I would write this function:

takeWhileNotDup :: Eq a => [a] -> [a]
takeWhileNotDup [] = []
takeWhileNotDup (x:xs) = x:go x xs
 where
 go _ [] = []
 go previous (x:xs)
 | previous /= x = x:go x xs
 | otherwise = []

Answer 2

Using type annotations in where or let clauses can be misleading. The a in go's type is not the same as the one in takeModified. Here's an example that shows that both as differ:

idPair :: (a, b) -> (a, b)
idPair (x,y) = (x, f y)
 where
 f :: a -> a
 f k = k

This compiles fine, even though we've used a, not b. So our as arent' really the same. This behaviour can be changed with -XScopedTypeVariables, but it's something to keep in mind. For example, if you had checked that none of the elements were the same as the first, you would have gotten a type error:

takeWhileNotfirst :: [a] -> [a]
takeWhileNotfirst [] = []
takeWhileNotfirst xs@(first:_) = first : go xs
 where
 go :: [a] -> [a] -- uh oh
 go (x:xs)
 | x == first = [] -- first is a, but x is another a!
 | otherwise = x : go xs
 go _ = []

We now get yelled on by GHC:

Example.hs:7:14:
 Couldn't match expected type `a1' with actual type `a'
 `a' is a rigid type variable bound by
 the type signature for takeWhileNotfirst :: [a] -> [a]
 at Test.hs:1:22
 `a1' is a rigid type variable bound by
 the type signature for go :: [a1] -> [a1] at Test.hs:5:11
 Relevant bindings include
 xs :: [a1] (bound at Test.hs:6:11)
 x :: a1 (bound at Test.hs:6:9)
 go :: [a1] -> [a1] (bound at Test.hs:6:5)
 first :: a (bound at Test.hs:3:23)
 xs :: [a] (bound at Test.hs:3:19)
 takeWhileNotfirst :: [a] -> [a] (bound at Test.hs:2:1)
 In the second argument of `(==)', namely `first'
 In the expression: x == first

In this case, go's type would be too general. So keep that in mind.

Other than that, I would prefer to use the simple cases (without where) first, so that the function doesn't get fenced by itself. But that's personal preference. However, there is already a function called elem :: Eq a => a -> [a] -> Bool in Prelude. You should try not to use names from Prelude, as it can lead to very interesting results if you change your code, e.g.

-- 1st version
go elem (x:xs)
 | elem == x = ...
-- some time later you refactor, but forget to change the second elem
-- 2nd version
go previous (x:xs)
 | elem == x = ... -- get yelled at by ghc, since "elem" is a function

But that's a problem in every programming language and not exclusive to Haskell.

I wonder whether I missed some basic library function and whether the function is idiomatic haskell:

Unfortunately there is no such library function, so that we can write it point-free for example. You can certainly build one with the same functionality, but it's clunky, and we need a helper:

takeWhileInclusive :: (a -> Bool) -> [a] -> [a]
takeWhileInclusive _ [] = []
takeWhileInclusive p (x:xs) = x : if p x then takeWhileInclusive p xs else []
takeModified :: Eq a => [a] -> [a]
takeModified xs = map fst (takeWhileInclusive (uncurry (/=)) (zip xs (tail xs)))

Yeah, that's not really easier to read. However, we can get rid of your helper, if we simply pattern match on two list elements:

takeModified :: Eq a => [a] -> [a]
takeModified (x:y:xs) = x : if x == y then [] else takeModified (y:xs)
takeModified xs = xs

Since you seem to prefer guards, we can also write the other cases first instead. Why? Because I prefer to use guards or patterns with where clauses last (personal preference, really):

takeModified :: Eq a => [a] -> [a]
takeModified [] = []
takeModified [x] = [x]
takeModified (x:y:xs) = 
 | x == y = [x]
 | otherwise = x : takeModified (y:xs)

Either way, your original code was mostly fine. But I would keep in mind that you can pattern match on multiple elements of a list.