[Haskell-cafe] function unique

Dan Weston westondan at imageworks.com
Thu Jul 12 17:33:11 EDT 2007


Philip Armstrong wrote:
> On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote:
>>   Ok so I played with the tweaked problem (Unix 'uniq'), and getting 
>> it to
>>   be lazy.  This seems to work:
> 
> It's slightly worse than that: unix uniq only eliminates *consecutive*
> identical lines from its input. If you want to eliminate all
> duplicates, you have to pipe your input through sort first.
> 
>>   testunique :: Eq a => [a] -> [a]
>>   testunique list = testunique' list []
>>      where testunique' :: Eq a => [a] -> [a] -> [a]
>>            testunique' [] elementssofar = []
>>            testunique' (x:xs) elementssofar | x `elem` elementssofar =
>>   (testunique' elementssofar xs)
>>                                             | otherwise = x : ( 
>> testunique'
>>   xs (x:elementssofar))
> 
> I suspect the author upthread had something more like this in mind:
> 
> uniq :: Eq a => [a] -> [a]
> uniq []     = []
> uniq (x:xs) = x : filter (x/=) (uniq2 xs)
> 
> Obviously a true 'unique' function has to traverse the entire list
> before it creates any output, as has been pointed out upthread.
> 
> Phil
> 

Close. Actually, the author upstream (i.e. me) had in mind:

 > uniq :: Eq a => [a] -> [a]
 > uniq []     = []
 > uniq (x:xs) = x : uniq (filter (/= x) xs)



More information about the Haskell-Cafe mailing list