A Rope is similar to a list, but has fast (constant time) concatenation at both ends, and fast concatenation of two Ropes.

It's slightly slower (O(n + operations) instead of O(n)) to iterate through, so you should convert it to a List if you plan to use it repeatedly.

Internally the Rope is a tree of lists.

An empty rope.

Create a rope with only one element:

singleton 1234 |> toList
--> [ 1234 ]


singleton "hi" |> toList
--> [ "hi" ]

Add an element to the end of a list.

append 1 (fromList [2,3]) |> toList
--> [2,3,1]
append 1 empty |> toList
--> [1]

Complexity: O(1)

Add an element to the front of a list.

prepend 1 (fromList [2,3]) |> toList
--> [1,2,3]
prepend 1 empty |> toList
--> [1]

Complexity: O(1)

Build a rope from a list.

Complexity: O(1)

Apply a function to every element of a rope.

map sqrt (fromList [1,4,9]) |> toList
--> [1,2,3]


map not (fromList [True,False,True]) |> toList
--> [False,True,False]

So map func (fromList [ a, b, c ]) is the same as fromList [ func a, func b, func c ]

Complexity: O(n)

Same as map but the function is also applied to the index of each element (starting at zero).

indexedMap Tuple.pair (fromList [ "Tom", "Sue", "Bob" ]) |> toList
--> [ ( 0, "Tom" ), ( 1, "Sue" ), ( 2, "Bob" ) ]

Complexity: O(n)

Reduce a rope from the left.

foldl (+) 0 (fromList [ 1, 2, 3 ])
--> 6


foldl (::) [] (fromList [ 1, 2, 3 ])
--> [ 3, 2, 1 ]

So foldl step state [1,2,3] is like saying:

state
    |> step 1
    |> step 2
    |> step 3

Complexity: O(n)

Reduce a rope from the right.

foldr (+) 0 (fromList [ 1, 2, 3 ])
--> 6


foldr (::) [] (fromList [ 1, 2, 3 ])
--> [ 1, 2, 3 ]

So foldr step state [1,2,3] is like saying:

state
    |> step 3
    |> step 2
    |> step 1

Keep elements that satisfy the test.

filter (\n -> modBy 2 n == 0) (fromList [1,2,3,4,5,6]) |> toList
--> [2,4,6]

Filter out certain values. For example, maybe you have a bunch of strings from an untrusted source and you want to turn them into numbers:

numbers : List Int
numbers =
    filterMap String.toInt [ "3", "hi", "12", "4th", "May" ]


-- numbers == [3, 12]

Convert a rope into the equivalent list.

Complexity: O(n)

Determine the length of a rope.

length (fromList [1,2,3])
--> 3

Reverse a rope.

reverse [ 1, 2, 3, 4 ] == [ 4, 3, 2, 1 ]

Figure out whether a rope contains a value.

member 9 (fromList [1,2,3,4])
--> False
member 4 (fromList [1,2,3,4])
--> True

Determine if all elements satisfy some test.

all (\n -> modBy 2 n == 0) (fromList [2,4])
--> True
all (\n -> modBy 2 n == 0) (fromList [2,3])
--> False
all (\n -> modBy 2 n == 0) (fromList [])
--> True

Determine if any elements satisfy some test.

any (\n -> modBy 2 n == 0) (fromList [ 2, 3 ])
--> True


any (\n -> modBy 2 n == 0) (fromList [ 1, 3 ])
--> False


any (\n -> modBy 2 n == 0) (fromList [])
--> False

Find the maximum element in a non-empty rope.

maximum (fromList [ 1, 4, 2 ])
--> Just 4


maximum (fromList [])
--> Nothing

Find the minimum element in a non-empty rope.

minimum (fromList [ 3, 2, 1 ])
--> Just 1


minimum (fromList [])
--> Nothing

Get the sum of the rope elements.

sum (fromList [ 1, 2, 3 ])
--> 6


sum (fromList [ 1, 1, 1 ])
--> 3


sum (fromList [])
--> 0

Get the product of the rope elements.

product (fromList [ 2, 2, 2 ])
--> 8


product (fromList [ 3, 3, 3 ])
--> 27


product (fromList [])
--> 1

Put two ropes together, the second after the first.

appendTo (fromList [ 1, 1, 2 ]) (fromList [ 3, 5, 8 ]) |> toList
--> [ 1, 1, 2, 3, 5, 8 ]


appendTo (fromList [ 'a', 'b' ]) (fromList [ 'c' ]) |> toList
--> [ 'a', 'b', 'c' ]

Complexity: O(1)

Put two ropes together, the first after the second.

prependTo (fromList [ 1, 1, 2 ]) (fromList [ 3, 5, 8 ]) |> toList
--> [ 3, 5, 8, 1, 1, 2 ]


prependTo (fromList [ 'a', 'b' ]) (fromList [ 'c' ]) |> toList
--> [ 'c', 'a', 'b' ]

Complexity: O(1)

Concatenate a bunch of ropes into a single rope:

concat (fromList [ fromList [ 1, 2 ], fromList [ 3 ], fromList [ 4, 5 ] ]) |> toList
--> [ 1, 2, 3, 4, 5 ]

Complexity: O(n), in practice it can be O(1) if the top level is the result of fromList

Map a given function onto a list and flatten the resulting lists.

concatMap f xs == concat (map f xs)

Determine if a rope is empty.

isEmpty (fromList [])
--> True