5

is stack is the same with List in F#? what about stack and sequence in F#? and what about queue?

2
  • Which "stack" and "queue" types are you referring to?
    – phoog
    May 6, 2011 at 16:41
  • List in F# are singly linked list.
    – gradbot
    May 6, 2011 at 16:48

3 Answers 3

7

Stacks and queues are abstract data types which can be implemented in several different ways. An F# list is implemented as an immutable singly-linked list. Since prepending or deleting an item from the front of a singly-linked list is a constant-time operation, F# lists make a good representation of a stack. But appending to a list is linear-time so they are less suitable for queues.

If you need an ephemeral stack then you might as well use the built-in System.Collections.Generic.Stack<T>. For a persistent stack, you could implement it yourself. This interface might be a good start:

type IStack<'A> =
    abstract member Push : 'A -> IStack<'A>
    abstract member Pop : unit -> 'A * IStack<'A>

or as a recursive data type:

type Stack<'A> = Stack of 'A * Stack<'A> | Empty

But to try and answer your question, although stacks and F# lists are not the same, lists are pervasive in functional programming and, because of their performance characteristics, they are used in places where a C# programmer would naturally reach for a stack. Since they are persistent, they are also a better fit for functional programs (which transform immutable data structures rather than modify mutable ones).

4

Sequence in F# is a lazily evaluated chain of objects, sort-of like IEnumerable

Here's a book to read. And another one.

Quoting: The Stack<'T> class can be thought of as a mutable version of the F# list.

3
  • 3
    Not just "sort-of like IEnumerable". seq<'T> is an an alias for IEnumerable<'T> - they're the same type. May 6, 2011 at 18:26
  • @Joel: Good point, but i did not find anything so specific in the spec: projects.ext.haxnet.org/~super/code/fsharp/… Could seq<T> be implementing more than just IEnumerable<T> in the future?
    – GregC
    May 7, 2011 at 5:23
  • 1
    We should be sure we're talking about the same thing. A sequence expression is a particular kind of computation expression that generates a seq<'T>. Other computation expressions do other things, but seq<'T> is really just an alias for IEnumerable<'T>. So sequence expressions might someday return an object that implements more than one interface, but I doubt that seq<'T> will change. May 7, 2011 at 5:44
0

If you mean stack and queues that are learned in a typical data structures course, then F# list and them are totally different.

2
  • yes, i mean that.. it seems stack have a same behaviour with List in F# doesn't it? May 6, 2011 at 17:12
  • you can use F# List to simulate a stack, but not possible for a queue.
    – Yin Zhu
    May 7, 2011 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.