A non-empty representation of a stack. top, removeTop, addOnTop mapTop are O(n)

in arguments

Empty Never (StackFilled ...) → stack is non-empty:

top : Empty Never (StackFilled element) -> element

in results

Empty Possibly (StackFilled ...) → stack could be empty

fromList : List element -> Empty Possibly (StackFilled element)

We can treat it like any Fillable.Empty:

import Fillable exposing (filled, Empty(..))
import Possibly exposing (Possibly)
import Stack exposing (StackFilled, top)


Fillable.empty : Stack Possibly element_ -- fine


toList : Empty possiblyOrNever_ (StackFilled element) -> List element
toList =
    \stack ->
        case stack of
            Filled ( top_, belowTop_ ) ->
                top_ :: belowTop_


            Empty _ ->
                []


[ "hi", "there" ] -- comes in as an argument
    |> Stack.fromList
    |> Fillable.map (filled >> top)
--: Empty String Possibly

Most operations also allow a different type for the top element → see StackWithTop

StackFilled with a different type for the top element:

top : Empty Never (StackWithTop top belowTopElement_) -> top

it's the result of:

• only
• topAndBelow
• fromTopAndBelow
• addOnTop
• mapTop
• map2TopAndDown

A stack with just 1 single element.

import Fillable
import Stack exposing (addOnTop)


Stack.only ":)"
--> Fillable.empty |> addOnTop ":)"

A stack from a top element and a List of elements below going down.

Convert from a tuple ( top, List belowElement ).

Currently equivalent to filled.

Convert a List element to a Empty Possibly (StackFilled element). The Lists head becomes top, its tail is shoved down below.

import Possibly exposing (Possibly)
import Fillable
import Stack exposing (topAndBelow)


[] |> Stack.fromList
--> Fillable.empty


[ "hello", "emptiness" ] |> Stack.fromList
--> topAndBelow "hello" [ "emptiness" ]
--: Empty Possibly (StackFilled String)

When constructing from known elements, always prefer

import Stack exposing (topAndBelow)


topAndBelow "hello" [ "emptiness" ]

The first value.

import Stack exposing (top, addOnTop)


Stack.only 3
    |> addOnTop 2
    |> top
--> 2

How many element there are.

import Stack exposing (addOnTop)


Stack.only 3
    |> addOnTop 2
    |> Stack.length
--> 2

Add an element to the front.

import Fillable
import Stack exposing (topAndBelow, addOnTop)


topAndBelow 2 [ 3 ] |> addOnTop 1
--> topAndBelow 1 [ 2, 3 ]


Fillable.empty |> addOnTop 1
--> Stack.only 1

Everything after the first value.

import Stack exposing (topAndBelow, addOnTop, stackOnTop, removeTop)


Stack.only 2
    |> addOnTop 3
    |> stackOnTop (topAndBelow 1 [ 0 ])
    |> removeTop
--> topAndBelow 0 [ 3, 2 ]
--: Empty Possibly (StackFilled number_)

Convert to a non-empty list tuple ( top, List belowElement ).

Currently equivalent to filling.

import Stack exposing (StackFilled, topAndBelow, splitTop)


topAndBelow "hi" [ "there", "👋" ]
    |> splitTop
--> ( "hi", topAndBelow "there" [ "👋" ] )
--: ( String, Empty Possibly (StackFilled String) )

Flip the order of the elements.

import Stack exposing (topAndBelow)


topAndBelow "l" [ "i", "v", "e" ]
    |> Stack.reverse
--> topAndBelow "e" [ "v", "i", "l" ]

Keep elements that satisfy a test.

import Stack exposing (topAndBelow)


topAndBelow 1 [ 2, 5, -3, 10 ]
    |> Stack.when (\x -> x < 5)
--> topAndBelow 1 [ 2, -3 ]
--: Empty Possibly (StackFilled number_)

Keep all filled values and drop all empty elements.

import Fillable exposing (filled)
import Stack exposing (topAndBelow)


topAndBelow Fillable.empty [ Fillable.empty ]
    |> Stack.whenFilled
--> Fillable.empty


topAndBelow (filled 1) [ Fillable.empty, filled 3 ]
    |> Stack.whenFilled
--> topAndBelow 1 [ 3 ]

As you can see, if only the top is filling a value, the result is non-empty.

Glue the elements of a stack to the end of another stack.

import Stack exposing (topAndBelow, stackOnTop)


topAndBelow 1 [ 2 ]
    |> stackOnTop (topAndBelow -1 [ 0 ])
--> topAndBelow -1 [ 0, 1, 2 ]

Prefer this over stackTypedOnTop if the piped stack is already known as non-empty or if both can be empty.

Glue the elements of an Empty possiblyOrNever/Never Stack to the end of a Stack.

import Fillable
import Stack exposing (topAndBelow, stackOnTop, stackTypedOnTop)


Fillable.empty
    |> stackTypedOnTop
        (topAndBelow 1 [ 2 ])
    |> stackOnTop
        (topAndBelow -2 [ -1, 0 ])
--> topAndBelow -2 [ -1, 0, 1, 2 ]

Prefer stackOnTop if the piped stack is already known as non-empty or if both are Possibly.

Glue together a bunch of stacks.

import Fillable
import Stack exposing (topAndBelow)


topAndBelow
    (topAndBelow 0 [ 1 ])
    [ topAndBelow 10 [ 11 ]
    , Fillable.empty
    , topAndBelow 20 [ 21, 22 ]
    ]
    |> Stack.concat
--> topAndBelow 0 [ 1, 10, 11, 20, 21, 22 ]

For this to return a non-empty stack, there must be a non-empty top stack.

Apply a function to every element.

import Stack exposing (topAndBelow)


topAndBelow 1 [ 4, 9 ]
    |> Stack.map negate
--> topAndBelow -1 [ -4, -9 ]

Change the top element based on its current value. Its type is allowed to change.

import Stack exposing (topAndBelow, mapTop)


topAndBelow 1 [ 4, 9 ]
    |> mapTop negate
--> topAndBelow -1 [ 4, 9 ]

Apply a function to every element of its removeTop.

import Stack exposing (topAndBelow, mapBelowTop)


topAndBelow 1 [ 4, 9 ]
    |> mapBelowTop negate
--> topAndBelow 1 [ -4, -9 ]

Reduce in a direction.

import LinearDirection exposing (LinearDirection(..))
import Stack exposing (topAndBelow)


topAndBelow 'l' [ 'i', 'v', 'e' ]
    |> Stack.foldFrom "" LastToFirst String.cons
--> "live"


topAndBelow 'l' [ 'i', 'v', 'e' ]
    |> Stack.foldFrom "" FirstToLast String.cons
--> "evil"

A fold in a direction where the initial result is the top.

import LinearDirection exposing (LinearDirection(..))
import Stack exposing (topAndBelow)


topAndBelow 234 [ 345, 543 ]
    |> Stack.fold FirstToLast max
--> 543

Convert it to a List.

import Stack exposing (topAndBelow)


topAndBelow 1 [ 7 ] |> Stack.toList
--> [ 1, 7 ]

Convert to a non-empty list tuple ( top, List belowElement ).

Currently equivalent to filling.

import Stack exposing (topAndBelow, toTopAndBelow)


topAndBelow "hi" [ "there", "👋" ]
    |> toTopAndBelow
--> ( "hi", [ "there", "👋" ] )

Combine every element in 2 stacks with a given function. If one stack is longer, its extra elements are dropped.

import Fillable
import Stack exposing (topAndBelow)


Stack.map2 (+)
    (topAndBelow 1 [ 2, 3 ])
    (topAndBelow 4 [ 5, 6, 7 ])
--> topAndBelow 5 [ 7, 9 ]


Stack.map2 Tuple.pair
    (topAndBelow 1 [ 2, 3 ])
   Fillable.empty
--> Fillable.empty

For StackWithTop top belowTopElement where top and belowTopElement have a different type, there's map2TopAndDown.

Combine the top and below elements of 2 stacks using given functions. If one stack is longer, its extra elements are dropped.

import Fillable
import Stack exposing (topAndBelow, map2TopAndDown)


map2TopAndDown Tuple.pair (+)
    (topAndBelow "hey" [ 0, 1 ])
    (topAndBelow "there" [ 1, 6, 7 ])
--> topAndBelow ( "hey", "there" ) [ 1, 7 ]


map2TopAndDown Tuple.pair (+)
    (topAndBelow 1 [ 2, 3 ])
   Fillable.empty
--> Fillable.empty

Use map2 if top and belowElement types match.