question about stack and list for F#

Question

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

Answer 1

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.

Answer 2

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).