• Effekt Logo Effekt Library
    • seq
      • Seq
        • Empty
        • Single
        • Deep
      • View
        • IsEmpty
        • View
      • NoSuchElement
      • IndexOutOfBounds
      • Digit
        • One
        • Two
        • Three
        • Four
      • Node
        • Leaf2
        • Leaf3
        • Node2
        • Node3
      • Finger
        • NoFinger
        • SingleFinger
        • DeepFinger
      • Tree
      • TreeView
        • TreeIsEmpty
        • TreeView
      • size
      • size
      • sizeDeep
      • size
      • size
      • deepFinger
      • deep
      • node2
      • node3
      • consFinger
      • cons
      • consFingerRight
      • consRight
      • unconsFinger
      • uncons
      • head
      • tail
      • unconsRightFinger
      • unconsRight
      • concatTree
      • concat
      • isEmpty
      • nonEmpty
      • reverse
      • index
      • update
      • each
      • each
      • eachReverse
      • eachReverse
      • toList
      • toSeq
      • Split
      • splitAt
      • insert
      • toTree
      • toTree
      • toSeq
      • toDigitNode
      • toDigitNode
      • toDigit
      • toList
      • map
      • map
    • seq
    • Jump to source: libraries/common/seq.effekt
      Example usage: examples/stdlib/seq
      This file implements the [[Seq]] type as a general purpose functional sequence.
      
      Implemented as a 2-3 finger tree, it supports
      - prepend and append in amortized O(1),
      - concat(m, n) in O(log(min(m, n)))
      - first and last in amortized O(1)
      - size in amortized O(1)
      
      More information on finger trees:
        https://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf
      • Seq [A]
      • Sequences of elements
        
        They are represented as 2-3 finger trees.
        • Empty
        • Single (value: A)
        • Deep (size: Int, prefix: Digit[A], middle: Tree[A], suffix: Digit[A])
      • View [A]
      • Result of splitting a sequence at the front or back.
        • IsEmpty
        • View (element: A, remainder: Seq[A])
      • NoSuchElement
      • Exception[NoSuchElement] is raised when accessing non-existing elements
        or splitting empty collections.
      • IndexOutOfBounds
      • Digit [A]
      • Internal grouping of 1-4 elements
        
        It is called digit since Okasaki (1998) calls finger trees "numerical operations".
        • One (value: A)
        • Two (first: A, second: A)
        • Three (first: A, second: A, third: A)
        • Four (first: A, second: A, third: A, fourth: A)
      • Node [A]
      • Internal representation of a 2-3 tree
        • Leaf2 (first: A, second: A)
        • Leaf3 (first: A, second: A, third: A)
        • Node2 (size: Int, first: Node[A], second: Node[A])
        • Node3 (size: Int, first: Node[A], second: Node[A], third: Node[A])
      • Finger [A, N]
      • Internal duplicate of Seq
        
        splitting into two type parameters is necessary since our MLton backend does
        not support mutually recursive data type declarations.
        • NoFinger
        • SingleFinger (value: Node[A])
        • DeepFinger (size: Int, prefix: N, middle: Finger[A, N], suffix: N)
      • Tree [A]
      • TreeView [A]
        • TreeIsEmpty
        • TreeView (element: Node[A], rest: Tree[A])
      • size [A] (node: Digit[A]): Int / {}
      • size [A] (node: Node[A]): Int / {}
      • sizeDeep [A] (node: Digit[Node[A]]): Int / {}
      • size [A] (tree: Tree[A]): Int / {}
      • size [A] (seq: Seq[A]): Int / {}
      • The size of the given sequence
      • deepFinger [A] (prefix: Digit[Node[A]], middle: Tree[A], suffix: Digit[Node[A]]): Tree[A] / {}
      • deep [A] (prefix: Digit[A], middle: Tree[A], suffix: Digit[A]): Seq[A] / {}
      • node2 [A] (first: Node[A], second: Node[A]): Node[A] / {}
      • node3 [A] (first: Node[A], second: Node[A], third: Node[A]): Node[A] / {}
      • consFinger [A] (head: Node[A], tail: Tree[A]): Tree[A] / {}
      • cons [A] (head: A, tail: Seq[A]): Seq[A] / {}
      • consFingerRight [A] (init: Tree[A], last: Node[A]): Tree[A] / {}
      • consRight [A] (init: Seq[A], last: A): Seq[A] / {}
      • unconsFinger [A] (seq: Tree[A]): TreeView[A] / {}
      • uncons [A] (seq: Seq[A]): View[A] / {}
      • head [A] (seq: Seq[A]): A / {Exception[NoSuchElement]}
      • tail [A] (seq: Seq[A]): Seq[A] / {Exception[NoSuchElement]}
      • unconsRightFinger [A] (seq: Tree[A]): TreeView[A] / {}
      • unconsRight [A] (seq: Seq[A]): View[A] / {}
      • concatTree [A] (first: Tree[A], middle: List[Node[A]], second: Tree[A]): Tree[A] / {}
      • concat [A] (first: Seq[A], second: Seq[A]): Seq[A] / {}
      • isEmpty [A] (seq: Seq[A]): Bool / {}
      • nonEmpty [A] (seq: Seq[A]): Bool / {}
      • reverse [A] (seq: Seq[A]): Seq[A] / {}
      • index [A] (seq: Seq[A], index: Int): A / {Exception[NoSuchElement]}
      • Random access
      • update [A] (seq: Seq[A], index: Int, value: A): Seq[A] / {Exception[NoSuchElement]}
      • Random access
      • each [A] (seq: Seq[A]) { consume: (A) => Unit }: Unit / {}
      • each [A] (seq: Seq[A]) { f: (A){Control} => Unit }: Unit / {}
      • eachReverse [A] (seq: Seq[A]) { consume: (A) => Unit }: Unit / {}
      • eachReverse [A] (seq: Seq[A]) { f: (A){Control} => Unit }: Unit / {}
      • toList [A] (seq: Seq[A]): List[A] / {}
      • toSeq [A] (l: List[A]): Seq[A] / {}
      • Split [A, R] (prefix: R, element: A, suffix: R)
      • splitAt [A] (seq: Seq[A], index: Int): Tuple2[Seq[A], Seq[A]] / {Exception[IndexOutOfBounds]}
      • insert [A] (seq: Seq[A], value: A, index: Int): Seq[A] / {Exception[IndexOutOfBounds]}
      • toTree [A] (digit: Digit[Node[A]]): Tree[A] / {}
      • toTree [A] (digit: List[Node[A]]): Tree[A] / {}
      • toSeq [A] (d: Digit[A]): Seq[A] / {}
      • toDigitNode [A] (n: Node[A]): Digit[Node[A]] / {}
      • toDigitNode [A] (n: List[A]): Digit[A] / {}
      • toDigit [A] (n: Node[A]): Digit[A] / {}
      • toList [A] (digit: Digit[A]): List[A] / {}
      • map [A, B] (seq: Seq[A]) { f: (A) => B }: Seq[B] / {}
      • map [A, B] (seq: Seq[A]) { f: (A){Control} => B }: Seq[B] / {}