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