Back to Questions
1.9k
views7
comments
Sequence transpose
f#

I'm trying to implement a single pass transpose operator for lazy sequences:

T

{ { 1, 1, 1, ... } { { 1, 2, 3, ... }

{ 2, 2, 2, ... } = { 1, 2, 3, ... }

{ 3, 3, 3, ... } { 1, 2, 3, ... }

... } ... }

and I came up with a solution which appears to work:

1
2
3
4
5
6
7
8
9
10

let transpose (outer: seq<#seq<_>>) : seq<seq<_>> = 

    seq { let enumerators = outer |> Seq.map (fun inner -> inner.GetEnumerator())

          let next() = enumerators |> Seq.forall (fun inner -> inner.MoveNext())

          while next() do

              yield seq { for inner in enumerators -> inner.Current } }

Running:

1
2
3
4
5
6
7
8

// Example 1. Correct

seq { for i in 1..100 (* nrows *) -> seq { for j in 1..100 (* ncols *) -> i } } 

|> Seq.transpose 

|> Seq.take 5;;

in fsi v1.9.6.16 seems to work correctly. The execution time seems to be independent of ncols and linearly dependent on nrows.

However I'm getting alreadyFinished exceptions being thrown by the internal MapEnumerator under certain situations. Also Seq.to_list is generating some weird results. Compare the behavior of example 1 to:

1
2
3
4
5
6
7
8

// Example 2. Zeroes

seq { for i in 1..100 -> seq { for j in 1..100 -> i } }

|> Seq.transpose 

|> Seq.to_list;;

which apparently zeroes out all the inner sequences and:

1
2
3
4
5
6
7
8

// Example 3. Exceptions

seq { for i in 1..100 -> seq { for j in 1..100 -> i } |> Seq.cache }

|> Seq.transpose 

|> Seq.to_list;;

which throws "Error: Enumeration already finished" exceptions.

I found code by generov implementing this operator with Seq.generate instead of sequence expressions: 4117

however, that code also illustrates the behavior from examples 2 and 3.

I suspect this is probably a bug but I thought I'd see if anyone here can see an obvious flaw in the algorithm before I report it. I have gotten a version of transpose to work on lists however it's not lazy and would result in multiple passes if I performed an operation over the result. I was researching LazyList however I noticed in the lazylist.fsi file in the source directory that the F# team intends to deprecate LazyList in favor of Seq and Seq.cache. Also, most of the functions like append for example don't appear to be tail-recursive.

So my last question is, what is the license for the PowerPack code? Can we copy and modify the LazyList library so long as we leave the Microsoft copyright in the file?

.

This code definitely looks wrong, see my failed solution at

[link:stackoverflow.com]

for detals why. It is very easy to screw up the side effect timing with seqs.

LazyList is getting un-deprecated, it will stay in the PowerPack, it is very useful.

I dunno the licensing details offhand, but the Beta1 <i>binary<i> powerpack license is linked here <A href="http://www.microsoft.com/downloads/details.aspx?displaylang=en&FamilyID=e475a670-9596-4958-bfa2-dc0ac29b4631">http://www.microsoft.com/downloads/details.aspx?displaylang=en&FamilyID=e475a670-9596-4958-bfa2-dc0ac29b4631</A> The PowerPack source is available as part of the latest 2008 CTP (eventually will be on CodePlex); see <A href="http://www.microsoft.com/downloads/details.aspx?FamilyID=7bb32f32-9fac-4f34-ad56-b0bda130cf00&displaylang=en">http://www.microsoft.com/downloads/details.aspx?FamilyID=7bb32f32-9fac-4f34-ad56-b0bda130cf00&displaylang=en</A> which has a link to its license.

By on 8/26/2009 12:50 PM ()

Thanks Brian,

I think I've found a solution with LazyList that has the performance I'm looking for.

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

module LazyList =

    open Microsoft.FSharp.Collections.LazyList

    

    let collect f m = concat (map f m)

  

    let forall p xs =

        // this should read "match first (not ``backward function composition`` p) xs with" 

        // but I can't get the less than character to properly escape. < isn't working.

        match first (not << p) xs with

        | None -> true

        | _ -> false

  

    type LazyListBuilder() =

        let zeroM() = empty()

        let returnM x = consf x zeroM

        let bindM x f = collect f x

        

        member this.Bind(m, f) = bindM m f

        member this.Return x = returnM x

        member this.Yield x = returnM x

        member this.Delay f = f()

        member this.For(m, f) = bindM (of_seq m) f

        member this.Zero() = zeroM()

        member this.Combine(m1, m2) = append m1 m2

  

    let lazylist = LazyListBuilder()

  

    let transpose outer = 

        let get_first = Option.get >> fst

        let get_second = Option.get >> snd

        let rec transpose' xs = lazylist {

            printfn "inner call"

            let inner = map get xs

            if forall Option.isSome inner then

                let heads = map get_first inner

                let tails = map get_second inner

                yield heads

                return! delayed (fun () -> transpose' tails) }

        transpose' outer

Until I read the post where I found generov's transpose implementation, I hadn't thought to use LazyList.delayed on the return! expression.

In fsi, lazylist { for i in 1..100 -> lazylist { for _ in 1..ncols -> i } } LazyList.transpose |> Seq.take n, prints "inner call" n times irregardless of the number of columns.

Any comments would be appreciated. Also, does the F# team intend to implement tail-recursive forms for the module functions (or does it already and I'm incorrectly interpreting the source code)?

By on 8/26/2009 3:52 PM ()

I've not scrutinized closely, but at a glance this looks right; nice.

> Also, does the F# team intend to implement tail-recursive forms for the module functions (or does it already and I'm incorrectly interpreting the source code)?

Not sure what you're asking here? Oh, we have an active bug (5267) tracking that e.g. LazyList.to_list is not tail-recursive, is that what you mean?

By on 8/26/2009 4:50 PM ()

Well on further testing, transpose is not scaling well with number of rows to the point where it's consuming .5GB for a million rows and taking a considerable amount of time. But I'm not working with data sets that large...yet...so it'll suffice for now.

Upon looking at the source for LazyList some of the functions don't appear to be in tail-recursive form like unfold:

1
2
3
4
5
6
7
8
9
10

let rec unfold f z = 

    lzy(fun () -> 

        match f z with

        | None       -> CellEmpty

        | Some (x,z) -> CellCons (x,unfold f z))

or map

1
2
3
4
5
6
7
8
9
10

let rec map f s = 

    lzy(fun () ->  

        match getcell s with

        | CellEmpty -> CellEmpty

        | CellCons(a,b) -> consc (f a) (map f b))

but since you mentioned LazyList.to_list's non-tail-recursive form a bug I assume these will be rewritten into a tail recursive form. Or am I misinterpreting the code? Or do I have an old version of the code? The source I have came with the May CTP for VS2008 addon.

The above code motivated me to ask about the license for modifying the PowerPack source, since I may run into stack overflows, and the only remedy, I assume, would be rewriting the code.

By on 8/26/2009 5:26 PM ()

The above code motivated me to ask about the license for modifying the PowerPack source, since I may run into stack overflows, and the only remedy, I assume, would be rewriting the code.

You can always write

let MyLazyListMap f l = ...

and call 'your map function' instead of the one in the PowerPack. I think the core type itself is fine, even if some of the associated module functions have poor implementations, and I expect you could easily author these functions (like map) yourself without reference to the PowerPack source code.

By on 8/26/2009 5:57 PM ()

True and I have written some operators (like transpose) in external assemblies. Just curious though, some of the functions in the LazyList module like lzy aren't exposed outside the module. Is that because the signature file excludes it? I haven't played around with signature files or read the spec closely to see how implementation and signature files interact. But nonetheless it appears enough functionality is exposed to recursively decompose a lazy list and build new ones lazily.

Also an update,

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

let transpose outer = 

    let rec transpose' xs = lazylist {

        if forall nonempty xs then

            let heads = map hd xs

            let tails = map tl xs

            return heads

            return! delayed (fun () -> transpose' tails) }

    transpose' outer

The above seems to perform faster and certainly use less memory by avoiding the allocation of large amounts of option objects.

For the next improvement I want to build the inner sequences lazily to emulate the behavior I illustrated at the top of the post. You should be able to transpose a potentially infinite list of potentially infinite lists but the current algorithm tries to consume the entire outer sequence.

By on 8/27/2009 3:46 PM ()

Update:

Caching the enumerators (or converting them to a list) via:

1
2

let enumerators = outer |> Seq.map (fun inner -> inner.GetEnumerator()) |> Seq.cache

alters the behavior of example 2 and only the first element of each inner sequence is zero. The rest are set to the appropriate value. Example 3 still throws exceptions.

By on 8/26/2009 12:42 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