Back to Questions
8.5k
views10
comments
Converting IEnumerator to list
f#

This is a design pattern that I am seeing quite often and I am wondering if there is a cleaner way to do this.

Basically I would like to take all the elements from an enumerable collection and convert it to a list. Here is a sample of code that I have written, though I think there must be a cleaner way to do this.

1
2
3
4
5
6

let enumerator_to_list(e:IEnumerator)  = e.Reset(); 
                                        let l = new List<_>() in 
                                           while e.MoveNext() do
                                                l.Add(e.Current)
                                            done;
                                            l.ToArray() |> List.of_array

Here is another example of what I am trying to do:

1
2
3
4
5
6
7

let node_children node = match node with
                        | null -> []
                        | cn -> let y = new List<XmlNode>() in
                                    for i = 0 to (cn:>XmlNode).ChildNodes.Count - 1 do
                                        y.Add(cn.ChildNodes.Item(i))
                                    done;
                                    y.ToArray() |> List.of_array

(Here the ChildNodes Property has an enumerator)

Is there an easier way to do this?

Thanks

Chris

.

This is how the List module does it:

1
2
3
4
5
6
7
8
9

let rec of_fresh_IEnumerator (e : IEnumerator<_>) = 
   let mutable res = [] in 
   while e.MoveNext() do
     res <- e.Current :: res
   done;
   List.rev res
  
let of_IEnumerable (c :> IEnumerable<_>) =
  of_fresh_IEnumerator (c.GetEnumerator())

This is from the F# library source, which is available to everyone in the distribution \lib\mllib\list.fs

By on 6/29/2006 9:55 AM ()

The use of mutable variables and while loops kills my inner child so here's one for the purely functional geeks.

1
2
3
4
5
6
7
8
9
10
11

let rec unfoldr f b =
  match f b with
    | Some (a, new_b) -> a :: unfoldr f new_b
    | None -> []


let enumueratorToList (e:IEnumerator<_>) =
  let func (e:IEnumerator<_>) = if e.MoveNext()
                                then Some (e.Current, e)
                                else None in
    unfoldr func e

well as least as pure as we can make it... given an IEnumerator

unfoldr would be a handy function to have in the standard library... essentially the reverse of a fold.
It goes from a value to a list rather than a list to a value.

1

val unfoldr : ('seed -> ('a * 'seed) option) -> 'seed -> 'a list
By on 7/1/2006 7:12 AM ()

While I agree with trying to save one's inner child, one problem with your recursive implementation is that it isn't tail recursive. I am sure there is some way to do something continuation passing to make it efficient without a while loop, though.

One of things I like about F# (and O'Caml) is that a loop can be used when necessary or convenient and then hidden as far as possible from all of our inner children :-)

By on 7/1/2006 1:32 PM ()

It is not tail recursive, this is true... and an issue in F#... but not an issue in Haskell which is where i nicked the definition from.

1
2
3
4
5
6
7

let rec unfoldl' acc f b =
  match f b with
    | Some (a, new_b) -> unfoldl' (a::acc) f new_b
    | None -> acc


let unfoldl f b = unfoldl' [] f b |> List.rev

Both the while solution and the unfoldl solution need to have the list reversed... unless we use a doubly linked list.

The unfoldr is nice if we are using lazy lists.

Personally I avoid loops at all costs as I much prefer higher order functions. They are almost always shorter to write and are more declarative.

By on 7/1/2006 2:01 PM ()

Reversing list is not need if acc is an accumulator function.

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

let comp f g x = f (g x)

let rec unfoldl' acc f b =

    let Cons x y = x :: y in

    match f b with

      | Some(a, new_b) -> unfoldl' ( comp acc (Cons a) ) f new_b

      | None -> acc

let unfoldl f b = unfoldl' id f b []

I prefer higher order function too.

By on 1/4/2010 1:05 AM ()

Nice work! The functions in the IEnumerable module are fantastically useful, particularly unfold, but also IEnumerable.to_list etc.

While we're on the topic, I'd suggest unfold should be added to the List, Array, LazyList modules (possibly also Set and Map).

Don

By on 7/1/2006 5:19 PM ()

Ah I didn't notice unfold was in the IEnumerable module... oh and it already exists for LazyList

So am I correct in understanding in that it hides a lazy list inside the IEnumerable interface (In the IEnumerable module)?

Why no fold for LazyList? There is 'folds' which seems interesting.

Not sure how I haven't noticed it before but the ordering for folds is somewhat inconsistent... and F# has inherited this from O'Caml for portability.

val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
and the same respectively for arrays

val fold : ('a -> 'b -> 'b) -> Set<'a> -> 'b -> 'b

val fold : ('key -> 'a -> 'c -> 'c) -> Map <'key,'a> -> 'c -> 'c
heh I need to watch out for that...

Folds might be handy for Array2 and Array3 too

By on 7/1/2006 7:55 PM ()

Thanks for the feedback - I've posted your comments to the internal F# team aliases to make sure we incorporate it.

Fold/folds on a lazy list in a strict language like F# is an interesting topic: we were discussing it at work during the week. fold_left on a lazy list becomes properly powerful (e.g. enough to define LazyList.map) if the accumulator is guaranteed to be a lazy computation (otherwise the entire lazy list must necessarily be evaluated as part of the fold, giving no chance to take the laziness of the list into the laziness of the accumulation). A sample signature of a lazy-preserving fold is:

1
2
3
4

 

val lazy_fold_left : (Lazy<'b> -> 'a -> 'b) -> 'b -> LazyList<'a> -> Lazy<'b>

rather than the all-too-strict:

1
2
3
4

 

val fold_left : ('b -> 'a -> 'b) -> 'b -> LazyList<'a> -> 'b

Try defining LasyList.map with the second and you'll see what I mean (it can't be done), though using the first to do so is no piece of cake.

(forgive me for the lack of full examples and explanation, or if I've made mistakes! Late at night over here :-) Navigating the lazy divide in a strict language is, however, a fascinating topic!)

Don

By on 7/2/2006 3:45 PM ()

I'm confused, I thought fold_right was ideal in a lazy language/lazy lists and fold_left is ideal in a strict language. And you want the computation of the accumulator to be *strict*.

foldl :: (a -> b -> a) -> a -> [ b ] -> a
foldl f a [] = a
foldl f a x:xs = foldl f (f a x) xs

(excuse my Haskell ;))

If the computation of the accumulator is lazy then you are just going to build up a huge series of deferred computations...

(f (f (f (f init x1) x2) x3) x4)

until you get to the end of the lazy list. So you really want the computation to be strict to avoid this space consumption.

foldr on the other hand makes good use of the lazyness

foldr :: (a -> b -> b) -> b -> [ a ] -> b
foldr f a [] = a
foldr f a x:xs = f x (foldr f a xs)

If you want to define Lazy.map with the mapping function 'g' then surely the function 'f' passed to the fold would be 'lazy cons' composed with 'g'... and you would want to pass that to foldr.
1) the ordering is kept
2) the first mapped value is available and the rest is delayed.
Neither of these two properties would hold for foldl with a lazy list and a lazy operator.

With lazy lists... foldr is useful wither operators like lazy cons, lazy list concatenation and lazy and/or

I believe I'm correct in saying that the time complexity of concatenating a list (lazy or not) of lazy lists using lazy concatenation and foldr will be linear, rather than the intuative quadratic.

I'm pretty sure you switched left with right... maybe that happened when you flipped the candle over to burn it from the other end ;).

However I will post my own caveats... this understanding is all coming from a Haskell background where everything is lazy... here you have to contend with intermixed lazyness and strictiness... as if lazyness on it's own didn't get crazy enough. I'm fairly certainly that my comments are correct here... and fortunately I am currently 5 hours behind GMT.

By on 7/2/2006 5:16 PM ()

Luckily I went to bed before I made any more mistakes! Yes, switched left and right (no, I mean right and left ;) )

1

val lazy_fold_right : ('a -> Lazy<'b> -> 'b) -> LazyList<'a> -> 'b -> Lazy<'b>

rather than the all-too-strict:

1

val fold_right : ('a -> 'b -> 'b) -> LazyList<'a> -> 'b -> 'b
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

open Lazy
open Stream (* nb. legacy name - still needed to access names 'Cons' and 'Nil' *)
open LazyList
  
let rec lazy_fold_right (f : 'a -> Lazy<'b> -> 'b) ll (s : 'b) : Lazy<'b> = lazy
  match LazyList.get ll with 
  | Cons(h,t) -> f h (lazy_fold_right f t s)
  | Nil -> s

let consl x xs = LazyList.consf x (fun () -> Lazy.force xs)
let swallow ll = LazyList.delayed (fun () -> Lazy.force ll)
let map f ll = lazy_fold_right (fun x xs -> consl (f x) xs) ll (empty()) |> swallow;;

Don

By on 7/3/2006 7:11 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