Back to Questions
1.2k
views2
comments
Sequences: underlying implementation and their value as generalizations
f#compiler

Two questions really: what underlying implementation (array, linked list, other) am I generating with a sequence comprehension such as,

1

  let s = {1 .. 10}

?

(I'm not able to match such a sequence against a (h :: t) pattern, so that makes me think a List is not underneath. But surely comprehensions would strain contiguous memory allocation if creating an enormous array.)

(Wait... are arrays contiguous in .NET? Mustn't they be to support linear lookup time?)

Second (and this will be harder to articulate), from a best-practices point of view, is there any value in striving to write F# such that the compiler infers sequence types over other, specialized types? It seems to me that a function that operates on a collection is more valuable (vis a vis its "general purposeness") if it accepts any enumerable collection (seq<>, or IEnumerable) rather than a specific implementation like Array or List.

--
Jeff S.

.

Hi,

You can have a look at fslib/ienumerable.fs file. Seq are a bit special, they are generators. This means you can store an infinite data. That's a kind of lazyness, and it's not comparable to lists or arrays. Seq is quite similar to LazyList (but is uncached).

1
2
3
4
5
6

> let l = {0..Int32.max_int};;
val l : seq<int>
> l;;
val it : seq<int> = seq [0; 1; 2; 3; ...]
> Seq.map (fun x -> x * x) l;;
val it : seq<int> = seq [0; 1; 4; 9; ...]

Laurent.

By on 8/6/2007 1:33 PM ()

Yes, sequences can potentially be computed on-demand. They map to "IEnumerable" in the .NET vocab.

Of course, a sequence might just be a list or an array, or some other concrete collection. They may also be a stream of data being read from an I/O connection or a database. It's possible that each time you traverse the sequence, a database connection may be reopened and a query executed.

It's often best practice to accept sequences as input to your API. However, consider the ramifications of this and make sure you document how often the sequence will be evaluated as part of your API design and implementation. For example, be aware that each time you traverse a sequence you might be recomputing the underlying results. If your API is going to do this multiple times then consider amortizing this cost (e.g. using Seq.cache_all) or documenting the fact that you intend to recompute.

Kind regards

don

By on 8/6/2007 2:25 PM ()

    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