Back to Questions
3.6k
views13
comments
lazy list, pattern matching in haskell style
f#haskell

The following is a straight translation of haskell's takeWhile. The question is, how do I make it lazy as in haskell ? As without the laziness, this function would easily result in stake overflow because the construct is not tail recursive.

1
2
3
4
5

let rec takeWhile p l =
  match l with
  |[] -> []
  |x::xs when p x-> x::takeWhile p xs
  |_->[]
.

Hi,
the best way for representing "lazy lists" in F# is to use sequence expressions. When a function returns list as the result, it cannot be lazy (because F# list is not lazy). If it returns the result as a sequence (seq<'a> type, which can be converted to list if needed) then it is lazy:

A direct translation would look like this:

1
2
3
4
5
6
7

 
let rec takeWhile p l =
  seq { match l with
        | x::xs when p x-> 
            yield x // return a single value
            yield! takeWhile p xs // return all values from the sequence
        | _->[] }

The seq { .. } syntax means that the code is a non-standard computation - in this case a lazy sequence.

T.

By on 11/15/2008 10:10 AM ()

thanks. I read about the Seq.take_while which use this approach.

The reason I asked though is actually coming from the following :

1
2
3
4

let rec partition l c =
 match l with
 |[] -> []
 |x::xs->[x::[for y in Seq.take_while ((<>) c) xs -> y]]::partition [ for y in drop_while ((<>) c) xs -> y] c;;

basically, I want to partition [1,2,2,5,1,4,5,6,7...] into [[1,2,2,5],[1,4,5,6,7],...]

It is easy to express in haskell style(well a bit inefficient because the takewhile/dropwhile on same portion but not an issue for me)

I find it hard to wrap in seq{}, especially when multiple such seq<'a> is composed together like the above.

Or may be it should be asked in another way:

how to do pattern matching and cons for seq<'a>

By on 11/15/2008 10:25 AM ()

Hi,
you can write the partition function such that it returns seq<list<'a>>, that is, it will eagerly generate a single list every time and then wait until the next list is needed.

1
2
3
4
5
6
7
8

 
let rec partition l c =
  seq {
    match l with
    |[] -> ()
    | x::xs->
        yield x::(Seq.take_while ((<>) c) xs |> List.of_seq) // easier way to convert
        yield! partition (drop_while ((<>) c) xs |> List.of_seq) c  };;

Implementing the overall operation as lazy would be difficult, because seq type doesn't support cons and pattern matching very well. You can write it in principle (using for example Seq.truncate), but that would be really inefficent, because sequences aren't very good for that. If you really need to make things lazy in this example, then you can use LazyList type from the FSharp.PowerPack.dll library. However, I think that most of the situations the solution above should be fine.

T.

By on 11/15/2008 11:34 AM ()

thanks tom and brian for the insightful examples.

haskell's list and laziness really shines in this type of thing, like brian's solution here:

[link:cs.hubfs.net]

which again is easy to reason yet suffers with the same issue of not tail recursive.

Another thing that is puzzling me is the above construct of

x::xs

even if I can somehow wrap it into the lazylist/seq equivalent of

(seq.head as x, seq.tail as xs)

since I subsequently use xs twice, would I run into problem that a sequence in this context cannot be consume twice ?

By on 11/15/2008 12:18 PM ()

You can typically consume/re-evaluate sequences, so there is no problem with "twice consuming" (other than if the sequence is backed by some computation/evaluation, that computation will typically be run twice).

It may be useful to toy around with code like the below:

1
2
3
4
5
6
7
8
9

let effectfulSeq = seq {
    for i in 1..4 do
        printfn "%d" i
        yield i}
let tail = Seq.skip 1 effectfulSeq
for i in tail do
    printfn "eval: %d" i
for i in tail do
    printfn "eval: %d" i
By on 11/15/2008 12:46 PM ()

does that mean if I have :

1

my_seq = orig_seq |> b |> c |> d ...

where b,c,d are some functions seq<'a> -> seq<'b>, seq<'b>->seq<'c> ...

multiple consuming my_seq would means redo the whole chain again and again ? that can be quite inefficient it terms of CPU time.

I was under the impression that in the case of haskell, it is cached some how, but need to go back to haskell's list to verify that.

By on 11/15/2008 5:10 PM ()

Haskell is lazy and pure everywhere and thus can cache everything (call-by-need). In F#, if you want that kind of caching, you must use LazyList (which is like a caching Seq - one where, if you have already evaluated the first few items, re-traversing will not re-evaluate). See also the "lazy" data type in F#; in effect, every value of type T in Haskell is equivalent to a value of type Lazy<T> in F#.

[link:research.microsoft.com]

By on 11/15/2008 5:23 PM ()

Just from the definition of Lazy, it seems to be some sort of 'computation' or monad. I tried to re-implement my takeWhile in the following form but runs into all sorts of compilation problem 

1
2
3
4
5

let rec takeWhile p (l:LazyList<'a>) =
  match l with
  | LazyList.Nil -> LazyList.Nil 
  | LazyList.Cons(a,b) when p a -> LazyList.cons(a, takeWhile p b)
  | _ -> LazyList.Nil

first the (l:LazyList<'a>) gives me some deprecation warning and asking me to use seq<_> and Seq.Cache instead

and the matching also doesn't work.

If I do want to use LazyList rather the the seq{..yield ..} style, what is the right way to implement the lazy takeWhile using LazyList ?

By on 11/15/2008 5:56 PM ()

ah, forgot that f# also use the curry form

1
2
3
4

let rec takeWhile p l =
  match l with
  | LazyList.Cons(a,b) when p a -> LazyList.cons a (takeWhile p b)
  | _ -> LazyList.of_list []

Not as concise as the Haskell syntax but very close.

Will LazyList be expanded a little to include the most frequently used list operation like the takeWhile, scanl, foldr etc. ? Or given the deprecated warning that I would better be using seq{} and Seq.cache ? But what would be the equivalent

By on 11/15/2008 6:42 PM ()

You can make a function tail-recursive without making your data structure lazy. Here's how to write takeWhile over eager lists with tail recursion.

1
2
3
4
5
6
7

let takeWhile p l =
  let rec takeWhile' xs acc =
  match xs with
    | x::xs when p x -> takeWhile' xs (x::acc)
    | _ -> acc

  List.rev (takeWhile' l [])

Also your takeWhile for lazy lists is still strict and consumes unbounded stack. You need to use LazyList.consf.

1
2
3
4

let rec takeWhile p l =
  match l with
  | LazyList.Cons(a,b) when p a -> LazyList.consf a (fun () -> takeWhile p b)
  | _ -> LazyList.empty ()
By on 11/15/2008 8:47 PM ()

thanks for the tail recursive optimization help.

what is the difference between LazyList.cons and LazyList.consf ?

By on 11/15/2008 11:13 PM ()

consf takes a delayed value for the tail of the list. This delays the recursion of takeWhile. Remember F#/OCaml is still a call-by-value language and we are just emulating laziness through abstraction. So in 

1

LazyList.cons a (takeWhile p b)

, the arguments of 

1

LazyList.cons

are evaluated before 

1

LazyList.cons

is called. Hence takeWhile is eagerly evaluated on the input list before the output list is constructed. So for example without consf this program would not terminate: 

1

infiniteList |> takeWhile (fun _ -> true)
By on 11/16/2008 12:20 PM ()

Seq does not play too well with pattern-matching and cons; you may prefer to use LazyList (in the power pack) or structure the code a little differently. See also [link:cs.hubfs.net] for some useful tricks.

By on 11/15/2008 11:23 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