git.iko.soy/elk
on ecaa5bd help sign in
elk/libraries/Native/List.js
321 lines 7.3 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;
7 var Utils = Elm.Native.Utils(elm);
9 // TODO: Improve Nil handling
10 // We can change places like: if (xs.ctor === 'Nil') ... to if (xs === Nil) ...
11 // but only if we're confident Nil can only be defined once.
12 // Currently (27Mar2013) each module can have different instantiations, so multiple Nil objects can exist
13 // (and if they're used interchangeably then direct object comparison fails where ctor doesn't).
14 // So, this can only be fixed when modules initialisation is also fixed.
15 // The performance overhead of the .ctor calls is 5-10% according to jsperf (depending on fn + list size)
16 // (on firefox 19)
18 // freeze is universally supported and as a singleton introduces little performance penalty
19 // for a small amount of object safety
20 var Nil = Object.freeze({ ctor:'Nil' });
22 // using freeze for every cons would be nice but is a huge (9x on firefox 19) performance penalty
23 function Cons(hd,tl) { return { ctor:"Cons", _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 !== 'Nil') {
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 === 'Nil') { return ys; }
57 var root = Cons(xs._0, Nil);
58 var curr = root;
59 xs = xs._1;
60 while (xs.ctor !== 'Nil') {
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 === 'Nil' ? throwError('head') : v._0; }
70 function tail(v) { return v.ctor === 'Nil' ? throwError('tail') : v._1; }
72 function last(xs) {
73 if (xs.ctor === 'Nil') { throwError('last'); }
74 var out = xs._0;
75 while (xs.ctor !== 'Nil') {
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 !== 'Nil') {
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 !== 'Nil') {
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 === 'Nil' ? throwError('foldl1') : foldl(f, xs._0, xs._1);
113 }
115 function foldr1(f, xs) {
116 if (xs.ctor === 'Nil') { 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 === 'Nil' ? throwError('scanl1') : scanl(f, xs._0, xs._1);
137 }
139 function filter(pred, xs) {
140 var arr = [];
141 while (xs.ctor !== 'Nil') {
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 !== 'Nil') {
151 out += 1;
152 xs = xs._1;
153 }
154 return out;
155 }
157 function member(x, xs) {
158 while (xs.ctor !== 'Nil') {
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 === 'Nil') 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 !== 'Nil') {
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 !== 'Nil') {
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 !== 'Nil' && ys.ctor !== 'Nil') {
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 !== 'Nil' && ys.ctor !== 'Nil') {
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 take(n, xs) {
222 var arr = [];
223 while (xs.ctor !== 'Nil' && n > 0) {
224 arr.push(xs._0);
225 xs = xs._1;
226 --n;
227 }
228 return fromArray(arr);
229 }
231 function drop(n, xs) {
232 while (xs.ctor !== 'Nil' && n > 0) {
233 xs = xs._1;
234 --n;
235 }
236 return xs;
237 }
239 function join(sep, xss) {
240 if (xss.ctor === 'Nil') return Nil;
241 var s = toArray(sep);
242 var out = toArray(xss._0);
243 xss = xss._1;
244 while (xss.ctor !== 'Nil') {
245 out = out.concat(s, toArray(xss._0));
246 xss = xss._1;
247 }
248 return fromArray(out);
249 }
251 function split(sep, xs) {
252 var out = Nil;
253 var array = toArray(xs);
254 var s = toArray(sep);
255 var slen = s.length;
256 if (slen === 0) {
257 for (var i = array.length; i--; ) {
258 out = Cons(Cons(array[i],Nil), out);
259 }
260 return out;
261 }
262 var temp = Nil;
263 for (var i = array.length - slen; i >= 0; --i) {
264 var match = true;
265 for (var j = slen; j--; ) {
266 if (!Utils.eq(array[i+j], s[j])) { match = false; break; }
267 }
268 if (match) {
269 out = Cons(temp,out);
270 temp = Nil;
271 i -= slen - 1;
272 } else {
273 temp = Cons(array[i+j], temp);
274 }
275 }
276 for (var j = slen-1; j--; ) {
277 temp = Cons(array[j], temp);
278 }
279 out = Cons(temp, out);
280 return out;
281 }
283 return elm.Native.List = {
284 Nil:Nil,
285 Cons:Cons,
286 toArray:toArray,
287 fromArray:fromArray,
288 range:range,
289 append:append,
291 head:head,
292 tail:tail,
293 last:last,
295 map:F2(map),
296 foldl:F3(foldl),
297 foldr:F3(foldr),
299 foldl1:F2(foldl1),
300 foldr1:F2(foldr1),
301 scanl:F3(scanl),
302 scanl1:F2(scanl1),
303 filter:F2(filter),
304 length:length,
305 member:F2(member),
306 reverse:reverse,
307 concat:concat,
309 all:F2(all),
310 any:F2(any),
311 zipWith:F3(zipWith),
312 zip:F2(zip),
313 sort:sort,
314 take:F2(take),
315 drop:F2(drop),
317 join:F2(join),
318 split:F2(split)
319 };
321};