Subject: FP: Counting Duplicats or Removing them using foldl

From: Shlomi Fish <[email-masked]>
Date: Wed, 15 May 2002 10:15:54 +0300 (IDT)

Danger! This post contains highly lethal Haskell code. Reading this post
can bring the unfortunate consequence of learning a little Haskell. Should
you decide to read this post, you should be warned that your ignorance of
Haskell is in jeopardy.

(sorry, Guy, could not resist)

foldl is a a very basic accumulator that takes a list of items and
accumulates them into one item, one by one. It uses a generic initial item
and a (\existing -> \new_item -> \new_existing) callback.

I wondered whether it was possible to use it to count duplicate items
(a.k.a Run-Length Encoding) or to remove consecutive duplicate items. When
I coded an RLE function as the equivalent of Muli's shell pipeline
converted to Perl script, I did not use foldl.

This task is in fact possible and I have the codelets here to prove it.
There's some duplicate code in them, but since Haskell is Strongly typed,
abstracting everything is relatively hard. I added several comments there,
but let me know if there's anything else you don't understand.

This code should be easily translatable to other functional languages:

-- Haskell in a nutshell
-- ---------------------
--
-- a:as append a at the beginning of the a:as list.
-- if cond then if-clause else else-clauses - need I say more?
-- a == b returns true if a is equal to b.
-- (a,b) - tuple of a and b
-- [] - the empty list
-- [a, b, c, d] - any list.
-- reverse mylist - reverses mylist
-- foldl - the foldl accumulator

-- Prototype for rem_last_duplicate
-- Accept a list and an element and return another list
rem_last_duplicate :: Ord a => [a] -> a -> [a]

-- This function ignores b assuming the latter is
-- the same as the first element of a.
rem_last_duplicate [] b = [b]
rem_last_duplicate (a:as) b =
    (if (a == b)
     then (a:as)
     else b:(a:as)
    )

remove_duplicates :: Ord a => [a] -> [a]

-- This function uses rem_last_duplicate and foldl
-- to remove duplicates in mylist. It's more of a macro
-- than a function.
remove_duplicates mylist =
    (reverse
        (foldl
            rem_last_duplicate
            []
            mylist
        )
    )

------------------------------------------------------

-- Haskell in a nutshell
-- ---------------------
--
-- a:as append a at the beginning of the a:as list.
-- if cond then if-clause else else-clauses - need I say more?
-- a == b returns true if a is equal to b.
-- (a,b) - tuple of a and b
-- [] - the empty list
-- [a, b, c, d] - any list.
-- reverse mylist - reverses mylist
-- foldl - the foldl accumulator

-- Prototype for count_last_duplicate
-- Parameter 1 : A list of (element, count) tuples
-- Parameter 2  : An extra element
--
-- Return: A list of (element, count) updated with the element.
count_last_duplicate :: Ord a => [(a,Integer)] -> a -> [(a,Integer)]

count_last_duplicate [] b = [(b,1)]
count_last_duplicate ((a,count):as) b =
    (if (a == b)
     then ((a,count+1):as)
     else (b,1):((a,count):as)
    )

rle :: Ord a => [a] -> [(a,Integer)]

-- This function uses count_last_duplicate and foldl to perform
-- a RLE encoding of a stream of tokens.
rle mylist =
    (reverse
        (foldl
            count_last_duplicate
            []
            mylist
        )
    )

----------------------------------------

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"