How to combine equal sequence elements (functional programming)?

Question

I want to write a function that takes in a sequence <1,1,2,2,3> and returns the sequence with equal elements grouped like <<1,1>, <2,2>, <3>>.

I'm using sequences, not lists, but some of the functions are similar. Some of the functions I am thinking of using are map, reduce, tabulate, filter, append etc..

Reduce takes in an associative function and returns the sequence that is "reduced" by that operator. So, reduce op+ 0 <1,2,3> = 6.

My first thought was to use map to raise the sequence by one level. So, <1,1,2,2,3> => <<1>,<1>,<2>,<2>,<3>>.

Then, I was thinking of using reduce, in which I create a function that takes pairs of elements like (x,y). If x == y, then I return else, I do nothing. But...this doesn't exactly work since the function has to return something of the same type in both cases.

Can someone give me some tips on the right path to take, like what higher order functions I could possibly use? I'm using SML but I'm not asking for anyone to give me a full blown answer so any high-level tips would be appreciated (in any functional language honestly)

Answer 1

I guess that the reduce function you are referring to is the same as the fold function in F#:

val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State

This takes a list of values, together with an initial state and a function that transforms the state while iterating through the values of the list.

You can do what you want in a single fold. There are a couple of things that you'll need to keep in the state. Imagine you are somewhere in the middle of 1,1,2,2,3 (say, on the second 2). Now you'll need:

• The value that you are currently collecting - that is 2
• A list of values containing the currently collected values - that is [2] (the first 2 from the sequence)
• A list of lists of values you collected previously - that is [ [1; 1] ].

You would start with an initial state -1, [], [] (using -1 as some value that won't appear in your input). Then you need to write the function that transforms the state based on a current value. This needs to handle a couple of situations:

• When the value is not the same as the values you've been collecting, you need to add the list of collected values to the list of lists (unless it is empty)
• When the value is the same, you need to add it to the list of values collected now and continue

Hopefully, this gives you enough information to figure out how to do this, without actually revealing the full source code!

Answer 2

If F# is your language, simply use the Seq.groupBy function:

input |> Seq.groupBy id |> Seq.map snd

Otherwise,

I assume that your language supports Seq.distinct, Seq.fold, Seq.map, and Seq.init. The F# version of these functions can be found in this document.

Then you can do the steps below:

1) Make a distinct seq of the input seq with Seq.distinct:

input |> Seq.distinct

2) Write a function that counts the number of occurrences of a value in a seq by using Seq.fold:

let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

3) Use the count function to decorate each element of the distinct seq with the number of its occurrences in the input seq:

Seq.map (fun x -> (x, count x input))

4) Finally, use Seq.init to replicate the equal elements:

Seq.map (fun (x, count) -> Seq.init count (fun i -> x))

The whole code:

let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

input
|> Seq.distinct
|> Seq.map (fun x -> (x, count x input))
|> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))

Answer 3

Don't know about the languages you are using, but from functional perspective, I would:

1. take sequence of distinct values
2. map each value in distinct sequence to filtered original sequence.

Pseudo code:

originalSequence = <1,1,2,2,3>
distinctSequence = originalSequnce.distinct() // <1,2,3>
result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>

Answer 4

In Haskell you have group and groupBy. They're made with a helper function called span. Standard ML unfortunately does not have as rich a standard library, so you'll have to create the function yourself. But you could use the same approach:

1. Define a function span that splits a list in two where the first part is the longest prefix for which some predicate is true, and the second part is the remainder of the list.

   fun span p [] = ...
     | span p (x::xs) = ... if p x then ... else ...
   

   For example,

   - span (fn n => n <= 3) [2,3,4,1,5]
   > val it = ([2,3], [4,1,5])
   

   This is a little difficult because you must somehow add x to the result of calling span p xs recursively, even though it returns a pair of lists; so you cannot just write x :: span p xs; you have to unpack the pair that is returned and return (x :: ys, zs) or (ys, x :: zs) (and stop recursing once p x is false).

2. Define a function groupBy that uses span. The function that groupBy uses should have two arguments unlike in span where p took one argument: The first one is the element with which to group, and the second is the subsequent elements.

   fun groupBy f [] = ...
     | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                           ... ys is the first group ...
                           ... groupBy f zs is the remaining groups ...
   

   Here it helps if the function f is curried, i.e. has type

   'a -> 'a -> bool
   

   since then it can be used like val (ys, zs) = span (f x) xs.

Feel free to ask follow-up questions if you want to use this approach.