
louise
Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.
Dernier runRéussi#1197 · main · 10 min 35 s
1Étoiles
0Forks
0Issues
| 1 | /// Immutable singly linked lists (`List` and its literals are in the |
| 2 | /// prelude). |
| 3 | |
| 4 | import std/array |
| 5 | |
| 6 | pub fn length :: xs: List<a> -> Int |
| 7 | { |
| 8 | count xs 0 |
| 9 | } |
| 10 | |
| 11 | fn count :: xs acc |
| 12 | { |
| 13 | match xs { [] -> acc, [_, ..rest] -> count rest (acc + 1) } |
| 14 | } |
| 15 | |
| 16 | pub fn reverse :: xs: List<a> -> List<a> |
| 17 | { |
| 18 | reverse_onto xs [] |
| 19 | } |
| 20 | |
| 21 | fn reverse_onto :: xs acc |
| 22 | { |
| 23 | match xs { [] -> acc, [x, ..rest] -> reverse_onto rest [x, ..acc] } |
| 24 | } |
| 25 | |
| 26 | pub 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 | |
| 31 | pub 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 | |
| 46 | pub 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 | |
| 51 | pub 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 | |
| 63 | pub 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`. |
| 70 | pub 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`. |
| 84 | pub 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 | |
| 96 | pub 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`. |
| 105 | pub fn range :: from: Int to: Int -> List<Int> |
| 106 | { |
| 107 | range_down to from [] |
| 108 | } |
| 109 | |
| 110 | fn 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. |
| 123 | pub 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. |
| 129 | pub 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. |
| 135 | pub 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`). |
| 143 | pub 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. |
| 150 | pub 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. |
| 166 | pub 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. |
| 172 | pub 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. |
| 186 | pub 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. |
| 198 | pub 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. |
| 218 | pub 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 | } |