tobogganSe connecter

louise

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

221 lignes · 5301 octetsBrut · Historique
1/// Immutable singly linked lists (`List` and its literals are in the
2/// prelude).
3
4import std/array
5
6pub fn length :: xs: List<a> -> Int
7{
8 count xs 0
9}
10
11fn count :: xs acc
12{
13 match xs { [] -> acc, [_, ..rest] -> count rest (acc + 1) }
14}
15
16pub fn reverse :: xs: List<a> -> List<a>
17{
18 reverse_onto xs []
19}
20
21fn reverse_onto :: xs acc
22{
23 match xs { [] -> acc, [x, ..rest] -> reverse_onto rest [x, ..acc] }
24}
25
26pub fn map :: xs: List<a> f: fn(a) -> b / <e> -> List<b> / <e>
27{
28 match xs { [] -> [], [x, ..rest] -> [f x, ..map rest f] }
29}
30
31pub fn filter :: xs: List<a> keep: fn(a) -> Bool / <e> -> List<a> / <e>
32{
33 match xs
34 { [] -> []
35 , [x, ..rest] -> if keep x
36 {
37 [x, ..filter rest keep]
38 }
39 else
40 {
41 filter rest keep
42 }
43 }
44}
45
46pub fn fold :: xs: List<a> acc: b f: fn(b, a) -> b / <e> -> b / <e>
47{
48 match xs { [] -> acc, [x, ..rest] -> fold rest (f acc x) f }
49}
50
51pub fn each :: xs: List<a> f: fn(a) -> () / <e> -> () / <e>
52{
53 match xs
54 { [] -> ()
55 , [x, ..rest] ->
56 {
57 f x
58 each rest f
59 }
60 }
61}
62
63pub fn append :: xs: List<a> ys: List<a> -> List<a>
64{
65 match xs { [] -> ys, [x, ..rest] -> [x, ..append rest ys] }
66}
67
68/// At most the first `n` elements: all of `xs` when `n >= length(xs)`,
69/// `[]` when `n <= 0`.
70pub fn take :: xs: List<a> n: Int -> List<a>
71{
72 if n <= 0
73 {
74 []
75 }
76 else
77 {
78 match xs { [] -> [], [x, ..rest] -> [x, ..take rest (n - 1)] }
79 }
80}
81
82/// `xs` without its first `n` elements: `[]` when `n >= length(xs)`, `xs`
83/// itself when `n <= 0`.
84pub fn drop :: xs: List<a> n: Int -> List<a>
85{
86 if n <= 0
87 {
88 xs
89 }
90 else
91 {
92 match xs { [] -> [], [_, ..rest] -> drop rest (n - 1) }
93 }
94}
95
96pub fn sum :: xs: List<a> -> a where Num<a>
97{
98 match xs
99 { [] -> panic "list.sum of an empty list"
100 , [x, ..rest] -> fold rest x fn acc y { acc + y }
101 }
102}
103
104/// `[from, from + 1, ..., to]`; empty when `to < from`.
105pub fn range :: from: Int to: Int -> List<Int>
106{
107 range_down to from []
108}
109
110fn range_down :: to from acc
111{
112 if to < from
113 {
114 acc
115 }
116 else
117 {
118 range_down (to - 1) from [to, ..acc]
119 }
120}
121
122/// Whether `test` holds for some element.
123pub fn any :: xs: List<a> test: fn(a) -> Bool / <e> -> Bool / <e>
124{
125 match xs { [] -> False, [x, ..rest] -> test x || any rest test }
126}
127
128/// Whether `test` holds for every element.
129pub fn all :: xs: List<a> test: fn(a) -> Bool / <e> -> Bool / <e>
130{
131 match xs { [] -> True, [x, ..rest] -> test x && all rest test }
132}
133
134/// The first element for which `test` holds, if any.
135pub fn find :: xs: List<a> test: fn(a) -> Bool / <e> -> Option<a> / <e>
136{
137 match xs
138 { [] -> None, [x, ..rest] -> if test x { Some(x) } else { find rest test } }
139}
140
141/// `f` applied to each element, the resulting lists concatenated in
142/// order (Haskell's `concatMap`).
143pub fn flat_map :: xs: List<a> f: fn(a) -> List<b> / <e> -> List<b> / <e>
144{
145 match xs { [] -> [], [x, ..rest] -> append (f x) (flat_map rest f) }
146}
147
148/// `f` applied to each element, while it succeeds: `Ok` with the
149/// values, or the first `Error`, after which `f` is not called again.
150pub fn try_map ::
151 xs: List<a>
152 f: fn(a) -> Result<b, x> / <e>
153 -> Result<List<b>, x> / <e>
154{
155 match xs
156 { [] -> Ok([])
157 , [x, ..rest] -> match f x
158 { Error(err) -> Error(err)
159 , Ok(y) -> match try_map rest f
160 { Ok(ys) -> Ok([y, ..ys]), Error(err) -> Error(err) }
161 }
162 }
163}
164
165/// The elements of `xs` and `ys` in pairs, up to the shorter list.
166pub fn zip :: xs: List<a> ys: List<b> -> List<(a, b)>
167{
168 match (xs, ys) { ([x, ..xs], [y, ..ys]) -> [(x, y), ..zip xs ys], _ -> [] }
169}
170
171/// The first and the second elements of the pairs, as two lists.
172pub fn unzip :: pairs: List<(a, b)> -> (List<a>, List<b>)
173{
174 match pairs
175 { [] -> ([], [])
176 , [(x, y), ..rest] ->
177 {
178 let (xs, ys) = unzip rest
179 ([x, ..xs], [y, ..ys])
180 }
181 }
182}
183
184/// `f` applied to the elements of `xs` and `ys` in pairs, up to the
185/// shorter list.
186pub fn zip_with ::
187 xs: List<a>
188 ys: List<b>
189 f: fn(a, b) -> c / <e>
190 -> List<c> / <e>
191{
192 match (xs, ys)
193 { ([x, ..xs], [y, ..ys]) -> [f x y, ..zip_with xs ys f], _ -> [] }
194}
195
196/// `xs` in ascending order. Stable: elements that compare `Eq` keep
197/// their original relative order.
198pub fn sort :: xs: List<a> -> List<a> where Ord<a>
199{
200 sort_by xs fn x y { compare x y }
201}
202
203/// `xs` ordered by `compare` (`Lt` means "comes first"). Stable, as
204/// `sort` is.
205///
206/// Sorts through `std/array`'s driftsort-style sort (issue #380).
207/// Measured against the top-down merge sort it replaced
208/// (tests/bench/sorts.lse, 100,000 elements, user instructions on one
209/// core, conversions included), the roundtrip wins on structured input
210/// and ties on random: random 731M -> 717M, low-cardinality 721M ->
211/// 392M, and, being run-adaptive where the merge sort was not, sorted
212/// 342M -> 44M, reverse 341M -> 51M, organ-pipe 361M -> 78M. It costs
213/// one O(n) conversion each way, and it is slower in the interpreter
214/// (about 8x on random data, where big sorts are rare); native is the
215/// target that matters. Which comparisons happen, and in what order,
216/// differs from the old sort: an effectful comparator observes a
217/// different sequence.
218pub fn sort_by :: xs: List<a> compare: fn(a, a) -> Order / <e> -> List<a> / <e>
219{
220 array.to_list (array.sort_by (array.from_list xs) compare)
221}