Back to Questions
1.2k
views8
comments
Self Terminating List Comprehensions?
f#functional

Hi, All,

I am an F# newbie (2 days of reading, 1 of programming) and am finding some things difficult to get my head round since I have only really programmed in VB.NET (some Java a while back).

What I want to do would be *easy* for me in an imperative language but it is driving me nuts in this functional language as I can't seem to see the wood for the trees.

I have managed to create lists using [1..10] and [for x in 1..10 -> x * x] style list comprehensions and then process the lists to do what I wanted. I knew how long these lists were going to be in advance. However, now I have a condition for terminating the length of the list i.e. the length of the list is not known in advance.

Taking the above example of creating a list of x^2 how would I create a list that is only as long as needs be so that the last entry in the list satisfies a condition such as being <110?

Let's say I called it xSquared. If I call it in this fashion:- xSquared(110) I would want the generated list to be <i>[1; 4; 9; 25; 36; 49; 64; 81; 100].<i> If I then called <b>xSquared(50)</b> I would want the generated list to be <i>[1; 4; 9; 25; 36; 49].<i> The function might not be as simple as this *squarer*, but could be a Fibonacci generator, for example. Could anyone give me any pointers - I am looking for an answer that DOES NOT use any imperative constructs like while loops etc. if possible - I can already do those [:)]. I'm guessing that recursion could be the key? Recursion!? Huh! - now that's a black art for me.[:(] Thanks in advance & Merry Christmas and a Happy New Year to all! Space Invader

.

The takeWhile function, I think, is what you want.

1

let xSquared x = Seq.initInfinite (fun n -> n*n) |> Seq.takeWhile (fun n -> n<x)
By on 12/26/2008 4:38 PM ()

Fixing the syntax in gneverov's excellent reply:

1

let xSquared x = Seq.init_infinite (fun n -> n*n) |> Seq.take_while (fun n -> n<x)
By on 12/29/2008 8:17 AM ()
1
2
3
4
5

let f x =
  let rec f i acc =
    let sq = i * i
    if sq > x then List.rev acc else f (i+1) (sq::acc)
  f 1 []
By on 12/25/2008 3:08 PM ()

let xSquared x =
seq {for i in 1 .. x do yield i * i}
|> Seq.to_list

By on 12/25/2008 9:57 AM ()

I believe seq {...} is a computation(i.e. sort of imperative).

let xSquaredList end = [1..end] |> List.map (fun x -> x*x)

That said, for many real world cases, seq {...} is usually faster and easier to construct.

By on 12/25/2008 11:55 AM ()

Hello,

Seq has some nice methods (unfold, windowed) and it's sadly, those methods doesn't released for all collections:

1
2
3
4
5

let sq lim = function
  | (i,ii) as prev when (i+1)*(i+1) < lim -> let i = i+1 in Some (prev, (i, i*i))
  | _ -> None

Seq.unfold (sq 110) (1,1)
By on 12/25/2008 11:30 PM ()

Hello,
Seq has some nice methods (unfold, windowed) and it's sadly, those methods doesn't released for all collections:

1
2
3
4
5

let sq lim = function
  | (i,ii) as prev when (i+1)*(i+1) < lim -> let i = i+1 in Some (prev, (i, i*i))
  | _ -> None

Seq.unfold (sq 110) (1,1)

Hi,

I'm unable to understand/use the above piece of code, can you explain it a bit...

thanks.

By on 12/31/2008 12:58 AM ()

Hello,

"let sq lim = function
..."
is equal to
"let sq lim it =
match it with
..."

"(sq 110)" is partial function application (curring), i.e. for that case it's equal to "(fun it -> sq 110 it)"

Seq.unfold has signature "('b -> ('a * 'b) option) -> 'b -> seq<'a>". For case when function sq returns option's member None, unfold terminate computation. Also, by contract, sq may return tuple "(something_to_push_to_resulted_sequence, something_to_push_to_next_call_to_sq)" wrapped in other option's member Some.

They simplest "unfold" implementation i can imagine (not for production [:)] ) is

1
2
3
4
5
6
7
8
9

let rec unfold f init =
  {
    match f init with
      | Some (prev,cur) -> 
        yield prev
        yield! unfold f cur
      | _ ->
        ()
  }
By on 12/31/2008 2:05 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