Abstract

Linked lists.

Perhaps surprisingly, linked lists actually work in a parallel language.

Synopsis

module type list = {
type list [n] 'a
val head [n] 'a: list [n] a -> a
val last [n] 'a: list [n] a -> a
val rev [n] 'a: list [n] a -> list [n] a
val from_array [n] 'a: [n]a -> list [n] a
val to_array [n] 'a: list [n] a -> [n]a
val sub [n] 'a: list [n] a -> i64 -> a
val (++) [n] [m] 'a: list [n] a -> list [m] a -> list [n + m] a
val map [n] 'a 'b: (a -> b) -> list [n] a -> list [n] b
val scan [n] 'a: (a -> a -> a) -> list [n] a -> list [n] a
val reduce [n] 'a: (a -> a -> a) -> a -> list [n] a -> a
val reduce_comm [n] 'a: (a -> a -> a) -> a -> list [n] a -> a
}
module list: list

Description

↑module type list
↑type list [n] 'a

A linked list with n elements of type a.

↑val head [n] 'a: list [n] a -> a

A partial function extracting the first element of the list. O(1).

↑val last [n] 'a: list [n] a -> a

A partial function extracting the last element of the list. O(1).

↑val rev [n] 'a: list [n] a -> list [n] a

Reverse list.

↑val from_array [n] 'a: [n]a -> list [n] a

Construct linked list from array. Work O(n), span O(1).

↑val to_array [n] 'a: list [n] a -> [n]a

Convert linked list to array. Work O(n log(n)), span O(log(n)).

↑val sub [n] 'a: list [n] a -> i64 -> a
↑val ++ [n] [m] 'a: list [n] a -> list [m] a -> list [n + m] a
↑val map [n] 'a 'b: (a -> b) -> list [n] a -> list [n] b

Apply function to every element of list.

↑val scan [n] 'a: (a -> a -> a) -> list [n] a -> list [n] a

Inclusive scan of list, given an associative operator. Work O(n log(n)), span O (log(n)).

↑val reduce [n] 'a: (a -> a -> a) -> a -> list [n] a -> a

Reduction with an associative operator.

↑val reduce_comm [n] 'a: (a -> a -> a) -> a -> list [n] a -> a

Reduction with an associative and commutative operator.

↑module list