Back to Questions
962
views8
comments
Negative sequences?
f#

Hi,

seq{0..100} works as expected but seq{100..0} is empty. I tried to write my own but got a little stuck (noob alert!). This is what I tried:

1
2
3
4

let negSeq start finish = 
    seq {
        for (i = start to finish) -> i
    }

and

1
2
3
4
5
6
7

let negSeq start finish = 
    seq {
        let mutable i = start;
        while i > finish do
            yield i;
            i <- i - 1;
    }

Neither of those compile. What's the right way to do this?

.

Here's a recursive version that works both ways:

1
2
3
4

let rec newSeq start finish =
    seq { yield start
          if start <> finish then
              yield! newSeq (start + sign(finish-start)) finish }
By on 6/10/2008 9:40 AM ()

Awesome! I was wondering if I could combine recursive functions and sequences. That's not going to create a new IEnumerable on each iteration, is it?

By on 6/10/2008 9:51 AM ()

Hi,

This doesn't create a new seq on each iteration. You can try this sample:

1

let rec foo: int seq = { yield! foo };;

This is an infinite loop. It doesn't allocate memory, and it doesn't use the stack (it's a tail recursion). Indeed, this is quite pretty. However, you get a warning since the compiler can't check soundness (this warning can be ignored).

Laurent.

By on 6/10/2008 4:26 PM ()

This doesn't create a new seq on each iteration.

I'm no IDL expert, but looking at the disassembly it does appear that multiple enumerators are getting generated.

Proof is in the performance, though.

<i>Original using internal sequences:<i> <code lang=fsharp> #light let rec newSeq start finish = seq { yield start if start <> finish then yield! newSeq (start + sign(finish-start)) finish } val newSeq : int -> int -> seq<int> > newSeq 1000000 0 |> Seq.fold1 (+);; Real: 00:00:02.183, CPU: 00:00:02.234, GC gen0: 2054, gen1: 3, gen2: 1 val it : int = 1784293664 </code> <i>Without internal sequences:<i> <code lang=fsharp> #light let fasterSeq start finish = seq { for i in start .. sign(finish-start) .. finish -> i } val fasterSeq : int -> int -> seq<int> > fasterSeq 1000000 0 |> Seq.fold1 (+);; Real: 00:00:00.325, CPU: 00:00:00.343, GC gen0: 0, gen1: 0, gen2: 0 val it : int = 1784293664 </code> Respectfully, J

By on 6/10/2008 5:43 PM ()
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

> let whileSeq start finish =
  let i = ref start
  seq { while !i > finish do
             yield !i
             do decr i };;

val whileSeq : int -> int -> seq<int>

> fasterSeq 1000000 0 |> Seq.fold1 (+);;

Real: 00:00:00.365, CPU: 00:00:00.312, GC gen0: 0, gen1: 0, gen2: 0

val it : int = 1784293664

> whileSeq 1000000 0 |> Seq.fold1 (+);;

Real: 00:00:02.767, CPU: 00:00:02.511, GC gen0: 708, gen1: 1, gen2: 0

val it : int = 1784293664

> newSeq 1000000 0 |> Seq.fold1 (+);;

Real: 00:00:02.36, CPU: 00:00:02.59, GC gen0: 654, gen1: 1, gen2: 0

val it : int = 1784293664

The recursive version is as fast as the explicit while loop.

By on 6/11/2008 1:22 AM ()

The correct way to do this is:

1

let negSeq = seq {100 .. -1 .. 0}

There should be a way to do this using yeild but its not completly obvious unless you reuse the orginal sequence expression, which feels like cheating:

1
2

let negSeq2 = seq { for i in seq {100.. -1 .. 0} do 
                        yield! i }

Cheers,
Rob

By on 6/10/2008 8:03 AM ()

There should be a way to do this using yeild but its not completly obvious unless you reuse the orginal sequence expression, which feels like cheating [...]

Hi Rob,

Perhaps you forgot "#light"? As I just discovered, computation workflows don't like non-light syntax. The following both work fine for me:

1
2
3

#light
let newseq3 = seq { for i in 100 .. -1 .. 0 -> i }
let newseq4 = seq { for i in 100 .. -1 .. 0 do yield i }

J

By on 6/10/2008 8:28 AM ()

Indeed - thanks for this precision ;)

By on 6/10/2008 8:57 AM ()

    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