Back to Questions
1.0k
views5
comments
A little quiz about groupBy
f#

Hi,

inspiring from this post [link:bugsquash.blogspot.com]

I am attempting to write a generic groupBy function and think it may be interesting to start a little quiz here.

The requirement is to write a groupBy function with the following signature:

groupBy (p:'a->'a->bool) (xs:['a]): ['a]::[['a]]

Note I use the list constructor shorthand here but it actualy means it can be list/array/seq/LazyList, the constraints are:

1. it must be able to handle things like [0..](infinite seq) or very long list/array(say [0..int64.Max])

2. it allows the consumption for the following case:

1
2
3
4

for x in groupBy ... do

  for y in x do printf y

and the input may not have breaks, i.e. the input could be [0..]

3. the predicate function p can be expensive

While I am able to sort of port the Haskell version here [link:hackage.haskell.org]

it is still not very satisfactory because of (3)

The strict translation of the C# equivalent(in the first link) failed (2)(i.e. nothing is printed when the input is [0..] as the intermediate result never ends)

I am wondering if there is an even better way.

.

inspiring from this post [link:bugsquash.blogspot.com]

Too bad his LazyList functions aren't lazy at all [:D] .

2. it allows the consumption for the following case:[...]

If this is your only use case, it would be way easier to collapse the nested sequence (e.g., 

1

[[1;2];[4;5]]

) into one including 'start bits' (

1

[Start,1;Continue,2;Start,4;Continue,5]

).

Three implementations for this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

type Iteration = Start | Continue
        
// using LazyList.scan
let iterate p =
    LazyList.scan (fun (_,prev) x ->
        let iter =
            match prev with
            | Some prev when not (p prev x) -> Continue
            | _ -> Start
        iter,Some x) (Start,None)
    >> LazyList.map (fun (iter,Some x) -> iter,x)
    
// using recursion on LazyLists
let iterate' p = 
    let rec loop prev = function
    | LazyList.Cons(x, xs) ->
        let iter =
            match prev with
            | Some prev when not (p prev x) -> Continue
            | _ -> Start
        LazyList.consDelayed (iter,x) (fun () -> loop (Some x) xs)
    | LazyList.Nil -> LazyList.empty ()
    loop None

// using Seq.scan
let iterateSeq p =
    Seq.scan (fun (_,prev) x ->
        let iter =
            match prev with
            | Some prev when not (p prev x) -> Continue
            | _ -> Start
        iter,Some x) (Start,None)
    >> Seq.skip 1 // differs from LazyList.scan
    >> Seq.map (fun (iter,Some x) -> iter,x)
1
2
3

> LazyList.ofSeq {0..System.Int32.MaxValue}
|> iterate (fun x y -> x / 3 <> y / 3);;val it : LazyList<Iteration * int> =
  seq [(Start, 0); (Continue, 1); (Continue, 2); (Start, 3); ...]

Now, if you insist on nested loops, you can reverse the transformation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

let rec split = function
| LazyList.Nil -> LazyList.empty ()
| xs ->
    let rec skipPart = function // strict
    | LazyList.Cons(_,(LazyList.Cons((Start,_),_) as xs)) -> xs
    | LazyList.Cons(_,xs) -> skipPart xs
    | nil -> nil
    let rec getPart = function // lazy
    | LazyList.Cons((_,x),(LazyList.Cons((Start,_),_) as xs)) -> LazyList.ofList [x] // LazyList.singleton, anyone?
    | LazyList.Cons((_,x),xs) -> LazyList.consDelayed x (fun () -> getPart xs)
    | nil -> LazyList.empty ()
    LazyList.consDelayed (getPart xs) (fun () ->
        split (skipPart xs))
        
let splitSeq (xs : _ seq) =


    seq {


        use ie = xs.GetEnumerator()


        let alive = ref <| ie.MoveNext()


        while !alive do


            yield seq {


                let numStarts = ref 0


                while !numStarts < 2 && !alive do


                    let (iter,x) = ie.Current


                    yield x


                    if iter = Start then


                        incr numStarts


                    if not (ie.MoveNext()) then


                        alive := false


            }


    }
1
2
3
4
5
6

> LazyList.ofSeq {0..System.Int32.MaxValue}
|> iterate (fun x y -> x / 5 <> y / 5)
|> splitval it : LazyList<LazyList<int>> =
  seq
    [seq [0; 1; 2; 3; ...]; seq [5; 6; 7; 8; ...]; seq [10; 11; 12; 13; ...];
     seq [15; 16; 17; 18; ...]; ...]

Note that, while the seq version will only work in your use case (i.e., fully consume each inner sequence (and only once) before moving to the next), split is actually able to 'fast-forward' to a given inner sequence.
Wow, this certainly was an interesting quiz!

By on 1/18/2010 3:18 PM ()

It is not the only use case, it really is a highlight that the solution should be able to spit out result even when the input is one whole group(and infinite).

Though as I mentioned, it is more as an excercise as there isn't that many real life case that have infinite sequence(may be the coming IObservable when the data source is say some remote data feed)

I would in general not using seq {} for this kind of generic function as I found that solution with seq{} doesn't play well for function composition(well they can always be wrapped with LazyList though)

thanks for the eye opening alternatives, I need to spend some time on them.

By on 1/18/2010 4:14 PM ()

forgot to include the everything is lazy version, this is much slower if I need to process every element (say sum of each group), comparing with the semi-lazy version

1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

let groupByL p l =
  let step x g (pre,head) =
    let split = consl (consl x (fun() -> LazyList.head (force g (Some x,true)))) (fun()-> force g (Some x,false)) 
    match pre with
      | None -> split
      | Some(y) -> 
        if p y x then 
          if head then split else force g (Some x, false) 
        else if head then consl (LazyList.empty()) (fun() -> split) else split
  (foldBack step l (fun _ -> consl (LazyList.empty()) (fun() -> LazyList.empty())) |> force) (None,true)
By on 1/18/2010 6:05 PM ()

How about this port of the prelude to OCaml
It reverses the list though, so I guess it's no good for seq / LazyList.

By on 1/17/2010 7:13 PM ()

that is basically the C# translation and can be done using seq {...}, just collect the 'head' group then spit it out. Or using a lazy foldBack for functional style(I skip the rev)

1
2
3
4
5
6
7
8
9
10
11

 

let groupByE p l =
  let step x g l =
    match l with
      | [] -> Lazy.force g [x]
      | y::ys -> 
        if p y x then Lazy.force g (x::l)
        else LazyList.consDelayed l (fun() -> Lazy.force g [x])
  (foldBack step l (fun x -> LazyList.cons x (LazyList.empty())) |> Lazy.force) []

The problem of this solution is if I don't have 'break' in the input sequence(i.e. it is one group), I cannot process anything until the very end(so it fails for seq {0..}). That said, this approach is almost the most efficient(I can think of) for sequences with reasonable breaks, as it seems that using lots of thunking and lazy/delay construct is very slow(if I have to process all the items anyway).

By on 1/18/2010 2:26 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper