git.iko.soy/elk
on eb2a032 help sign in
elk/libraries/Native/List.js
363 lines 8.2 kB history raw
1Elm.Native.List = function(elm) {
2 "use strict";
4 elm.Native = elm.Native || {};
5 if (elm.Native.List) return elm.Native.List;
6 if ('values' in Elm.Native.List)
7 return elm.Native.List = Elm.Native.List.values;
9 var Utils = Elm.Native.Utils(elm);
11 // TODO: Improve Nil handling
12 // We can change places like: if (xs.ctor === '[]') ... to if (xs === Nil) ...
13 // but only if we're confident Nil can only be defined once.
14 // Currently (27Mar2013) each module can have different instantiations, so multiple Nil objects can exist
15 // (and if they're used interchangeably then direct object comparison fails where ctor doesn't).
16 // So, this can only be fixed when modules initialisation is also fixed.
17 // The performance overhead of the .ctor calls is 5-10% according to jsperf (depending on fn + list size)
18 // (on firefox 19)
20 var Nil = { ctor:'[]' };
22 // using freeze for every cons would be nice but is a huge (9x on firefox 19)
23 // performance penalty
24 function Cons(hd,tl) { return { ctor:"::", _0:hd, _1:tl }; }
26 function throwError(f) {
27 throw new Error("Function '" + f + "' expects a non-empty list!");
28 }
30 function toArray(xs) {
31 var out = [];
32 while (xs.ctor !== '[]') {
33 out.push(xs._0);
34 xs = xs._1;
35 }
36 return out;
37 }
39 function fromArray(arr) {
40 var out = Nil;
41 for (var i = arr.length; i--; ) {
42 out = Cons(arr[i], out);
43 }
44 return out;
45 }
47 function range(lo,hi) {
48 var lst = Nil;
49 if (lo <= hi) {
50 do { lst = Cons(hi,lst) } while (hi-->lo);
51 }
52 return lst
53 }
55 function append(xs,ys) {
56 if (typeof xs === "string") { return xs.concat(ys); }
57 if (xs.ctor === '[]') { return ys; }
58 var root = Cons(xs._0, Nil);
59 var curr = root;
60 xs = xs._1;
61 while (xs.ctor !== '[]') {
62 curr._1 = Cons(xs._0, Nil);
63 xs = xs._1;
64 curr = curr._1;
65 }
66 curr._1 = ys;
67 return root;
68 }
70 function head(v) { return v.ctor === '[]' ? throwError('head') : v._0; }
71 function tail(v) { return v.ctor === '[]' ? throwError('tail') : v._1; }
73 function last(xs) {
74 if (xs.ctor === '[]') { throwError('last'); }
75 var out = xs._0;
76 while (xs.ctor !== '[]') {
77 out = xs._0;
78 xs = xs._1;
79 }
80 return out;
81 }
83 function map(f, xs) {
84 var arr = [];
85 while (xs.ctor !== '[]') {
86 arr.push(f(xs._0));
87 xs = xs._1;
88 }
89 return fromArray(arr);
90 }
92 // f defined similarly for both foldl and foldr (NB: different from Haskell)
93 // ie, foldl : (a -> b -> b) -> b -> [a] -> b
94 function foldl(f, b, xs) {
95 var acc = b;
96 while (xs.ctor !== '[]') {
97 acc = A2(f, xs._0, acc);
98 xs = xs._1;
99 }
100 return acc;
101 }
103 function foldr(f, b, xs) {
104 var arr = toArray(xs);
105 var acc = b;
106 for (var i = arr.length; i--; ) {
107 acc = A2(f, arr[i], acc);
108 }
109 return acc;
110 }
112 function foldl1(f, xs) {
113 return xs.ctor === '[]' ? throwError('foldl1') : foldl(f, xs._0, xs._1);
114 }
116 function foldr1(f, xs) {
117 if (xs.ctor === '[]') { throwError('foldr1'); }
118 var arr = toArray(xs);
119 var acc = arr.pop();
120 for (var i = arr.length; i--; ) {
121 acc = A2(f, arr[i], acc);
122 }
123 return acc;
124 }
126 function scanl(f, b, xs) {
127 var arr = toArray(xs);
128 arr.unshift(b);
129 var len = arr.length;
130 for (var i = 1; i < len; ++i) {
131 arr[i] = A2(f, arr[i], arr[i-1]);
132 }
133 return fromArray(arr);
134 }
136 function scanl1(f, xs) {
137 return xs.ctor === '[]' ? throwError('scanl1') : scanl(f, xs._0, xs._1);
138 }
140 function filter(pred, xs) {
141 var arr = [];
142 while (xs.ctor !== '[]') {
143 if (pred(xs._0)) { arr.push(xs._0); }
144 xs = xs._1;
145 }
146 return fromArray(arr);
147 }
149 function length(xs) {
150 var out = 0;
151 while (xs.ctor !== '[]') {
152 out += 1;
153 xs = xs._1;
154 }
155 return out;
156 }
158 function member(x, xs) {
159 while (xs.ctor !== '[]') {
160 if (Utils.eq(x,xs._0)) return true;
161 xs = xs._1;
162 }
163 return false;
164 }
166 function reverse(xs) { return fromArray(toArray(xs).reverse()); }
168 function concat(xss) {
169 if (xss.ctor === '[]') return xss;
170 var arr = toArray(xss);
171 var xs = arr[arr.length-1];
172 for (var i = arr.length-1; i--; ) {
173 xs = append(arr[i], xs);
174 }
175 return xs;
176 }
178 function all(pred, xs) {
179 while (xs.ctor !== '[]') {
180 if (!pred(xs._0)) return false;
181 xs = xs._1;
182 }
183 return true;
184 }
186 function any(pred, xs) {
187 while (xs.ctor !== '[]') {
188 if (pred(xs._0)) return true;
189 xs = xs._1;
190 }
191 return false;
192 }
194 function zipWith(f, xs, ys) {
195 var arr = [];
196 while (xs.ctor !== '[]' && ys.ctor !== '[]') {
197 arr.push(A2(f, xs._0, ys._0));
198 xs = xs._1;
199 ys = ys._1;
200 }
201 return fromArray(arr);
202 }
204 function zip(xs, ys) {
205 var arr = [];
206 while (xs.ctor !== '[]' && ys.ctor !== '[]') {
207 arr.push(Utils.Tuple2(xs._0, ys._0));
208 xs = xs._1;
209 ys = ys._1;
210 }
211 return fromArray(arr);
212 }
214 function sort(xs) {
215 function cmp(a,b) {
216 var ord = Utils.compare(a,b).ctor;
217 return ord=== 'EQ' ? 0 : ord === 'LT' ? -1 : 1;
218 }
219 return fromArray(toArray(xs).sort(cmp));
220 }
222 function nth(xs, n) {
223 return toArray(xs)[n];
224 }
226 function take(n, xs) {
227 var arr = [];
228 while (xs.ctor !== '[]' && n > 0) {
229 arr.push(xs._0);
230 xs = xs._1;
231 --n;
232 }
233 return fromArray(arr);
234 }
236 function drop(n, xs) {
237 while (xs.ctor !== '[]' && n > 0) {
238 xs = xs._1;
239 --n;
240 }
241 return xs;
242 }
244 function repeat(n, a) {
245 var arr = [];
246 while (n > 0) {
247 arr.push(a);
248 --n;
249 }
250 return fromArray(arr);
251 }
253 function join(sep, xss) {
254 if (typeof sep === 'string') return toArray(xss).join(sep);
255 if (xss.ctor === '[]') return Nil;
256 var s = toArray(sep);
257 var out = toArray(xss._0);
258 xss = xss._1;
259 while (xss.ctor !== '[]') {
260 out = out.concat(s, toArray(xss._0));
261 xss = xss._1;
262 }
263 return fromArray(out);
264 }
266 function split(seperator, list) {
267 var array = toArray(list);
268 var alen = array.length;
269 if (alen === 0) {
270 // splitting an empty list is a list of lists: [[]]
271 return Cons(Nil,Nil);
272 }
274 var sep = toArray(seperator);
275 var seplen = sep.length;
276 if (seplen === 0) {
277 // splitting with an empty sep is a list of all elements
278 // Same as (map (\x -> [x]) list)
279 var out = Nil;
280 for (var i = alen; i--; ) {
281 out = Cons(Cons(array[i],Nil), out);
282 }
283 return out;
284 }
286 var matches = [-seplen];
287 var sepStart = sep[0];
288 var len = alen - seplen + 1;
289 for (var i = 0; i < len; ++i) {
290 if (Utils.eq(array[i], sepStart)) {
291 var match = true;
292 for (var j = seplen; --j; ) {
293 if (!Utils.eq(array[i+j], sep[j])) { match = false; break; }
294 }
295 if (match) {
296 matches.push(i);
297 i += seplen - 1;
298 }
299 }
300 }
302 // shortcut in case of no matches
303 if (matches.length === 0) {
304 return Cons(list,Nil);
305 }
307 var out = Nil;
308 var index = alen - 1;
309 for (var i = matches.length; i--; ) {
310 var temp = Nil;
311 var stop = matches[i] + seplen - 1;
312 for ( ; index > stop; --index ) {
313 temp = Cons(array[index], temp);
314 }
315 out = Cons(temp,out);
316 index -= seplen;
317 }
318 return out;
319 }
321 Elm.Native.List.values = {
322 Nil:Nil,
323 Cons:Cons,
324 cons:F2(Cons),
325 toArray:toArray,
326 fromArray:fromArray,
327 range:range,
328 append:append,
330 head:head,
331 tail:tail,
332 last:last,
334 map:F2(map),
335 foldl:F3(foldl),
336 foldr:F3(foldr),
338 foldl1:F2(foldl1),
339 foldr1:F2(foldr1),
340 scanl:F3(scanl),
341 scanl1:F2(scanl1),
342 filter:F2(filter),
343 length:length,
344 member:F2(member),
345 reverse:reverse,
346 concat:concat,
348 all:F2(all),
349 any:F2(any),
350 zipWith:F3(zipWith),
351 zip:F2(zip),
352 sort:sort,
353 nth:F2(nth),
354 take:F2(take),
355 drop:F2(drop),
356 repeat:F2(repeat),
358 join:F2(join),
359 split:F2(split)
360 };
361 return elm.Native.List = Elm.Native.List.values;
363};