Seq.unfold explanation in F#

Question

I am trying to create a sequence lazily by using F#.

The sequence is defined as follows:

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Here is what I have so far but it dosn't seem to work:

let tri_seq = 1.0 |> Seq.unfold (fun x -> match x with                                         
                                          | _ -> Some (x, 0.5*x*(x + 1.0)))

Thank you very much who can help me figure out how unfold works. Thanks

Edit: I marked the first answer as correct but it dosnt work, however I slightly modified it and it worked.

let tri_seq = 1.0 |> Seq.unfold (fun x -> Some (0.5 * x * (x + 1.0),x + 1.0))

score 8 · Accepted Answer · edited Feb 10 '09 at 20:11

8

First off, why do you use match if you've got only one case?

let tri_seq = 1.0 |> Seq.unfold (fun x -> Some (x, 0.5 * x * (x + 1.0)))

Second, what “doesn't seem to work”? Are you aware that you produce an infinite list?

/Edit: For completeness’ sake, here’s the correct solution, which the OP found himself and posted as a comment:

let tri_seq = 
    1.0 |> Seq.unfold (fun x -> Some (0.5 * x * (x + 1.0), x + 1.0))

edited Feb 10 '09 at 20:11

Brian

117,631
17
236
300

answered Feb 10 '09 at 18:57

Konrad Rudolph

530,221
131
937
1,214

I tried that, but the sequence just returns one.. > tri_seq;; val it : seq = seq [1.0; 1.0; 1.0; 1.0; ...] – masfenix Feb 10 '09 at 18:59
let tri_seq = 1.0 |> Seq.unfold (fun x -> Some (0.5 * x * (x + 1.0),x + 1.0)) is what i needed. Thankyou very much. – masfenix Feb 10 '09 at 19:05

score 4 · Answer 2 · answered Feb 10 '09 at 23:51

4

Another alternative to the code that Brian posted is to use recursion instead of imperative 'while' loop:

let tri = 
  let rec loop(n, diff) = seq { 
    yield n        
    yield! loop(n + diff, diff + 1.0) }
  loop(1.0, 2.0)
printfn "%A" (tri |> Seq.take 10 |> Seq.to_list)

It is far less efficient (so you have to be a bit careful here...), but it is more idiomatic functional solution, so it may be easier to see what the code does.

answered Feb 10 '09 at 23:51

Tomas Petricek

240,744
19
378
553

Thankyou, but i have no idea what the "Seq { }" does, not "yield" keyword, and lets not talk about the "!". If you can take some time to explain, it would be appreciated! – masfenix Feb 10 '09 at 23:56
Not an expert, but Seq {} means make me a sequence out of this. yield is same as C# - means send back value and wait for calling code to ask for next. yield! is (I believe) like Seq.concat - flattens the seq returned from recursive call and does a yield on each element. – Benjol Feb 13 '09 at 10:30
a bit of effort can be made to have at least `loop` be tail recursive, otherwise this is not going to scale anywhere – pqnet Jan 22 '18 at 14:41
1

@pqnet The F# compiler actually handles recursive `seq` expressions nicely, so this pattern works fine (it's not like `foreach(x in y) yield x` in C# which would be problematic) – Tomas Petricek Jan 22 '18 at 22:41
@TomasPetricek you are right, the function is actually a tail call since sequences are lazy, and `loop` returns a sequence, which is then returned as a continuation of the current sequence. If `yield` and `yield!` were in opposite order, that would be problematic, but like this it is possible to optimize – pqnet Jan 23 '18 at 10:43

score 3 · Answer 3 · answered Feb 10 '09 at 19:12

3

Here is an alternative:

let tri = seq {
    let n = ref 1.0
    let diff = ref 2.0
    while true do
        yield !n
        n := !n + !diff
        diff := !diff + 1.0
    }

printfn "%A" (tri |> Seq.take 10 |> Seq.to_list)

answered Feb 10 '09 at 19:12

Brian

117,631
17
236
300

score 2 · Answer 4 · edited May 08 '16 at 13:23

I know this is a pretty old one, but i cant figure out why using float when you are sure that x * (x + 1) is an even number and indeed divisible by 2. So I would simply use this one instead (not much difference i know but at least you have an int seq):

let tri_seq = 1 |> Seq.unfold (fun x -> Some (x * (x + 1) / 2 , x + 1)) 

tri_seq |> Seq.take 6 |> Seq.toList //[1; 3; 6; 10; 15; 21]

fiddle

(Unless you dealing with huge numbers of course....)

Seq.unfold explanation in F#

4 Answers4

Linked