git.iko.soy/elk
on 4bb23bc help sign in
elk/libraries/Native/List.js
325 lines 7.5 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 === 'Nil') ... 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 // freeze is universally supported and as a singleton introduces little performance penalty
21 // for a small amount of object safety
22 var Nil = Object.freeze({ ctor:'Nil' });
24 // using freeze for every cons would be nice but is a huge (9x on firefox 19) performance penalty
25 function Cons(hd,tl) { return { ctor:"Cons", _0:hd, _1:tl }; }
27 function throwError(f) {
28 throw new Error("Function '" + f + "' expects a non-empty list!");
29 }
31 function toArray(xs) {
32 var out = [];
33 while (xs.ctor !== 'Nil') {
34 out.push(xs._0);
35 xs = xs._1;
36 }
37 return out;
38 }
40 function fromArray(arr) {
41 var out = Nil;
42 for (var i = arr.length; i--; ) {
43 out = Cons(arr[i], out);
44 }
45 return out;
46 }
48 function range(lo,hi) {
49 var lst = Nil;
50 if (lo <= hi) {
51 do { lst = Cons(hi,lst) } while (hi-->lo);
52 }
53 return lst
54 }
56 function append(xs,ys) {
57 if (typeof xs === "string") { return xs.concat(ys); }
58 if (xs.ctor === 'Nil') { return ys; }
59 var root = Cons(xs._0, Nil);
60 var curr = root;
61 xs = xs._1;
62 while (xs.ctor !== 'Nil') {
63 curr._1 = Cons(xs._0, Nil);
64 xs = xs._1;
65 curr = curr._1;
66 }
67 curr._1 = ys;
68 return root;
69 }
71 function head(v) { return v.ctor === 'Nil' ? throwError('head') : v._0; }
72 function tail(v) { return v.ctor === 'Nil' ? throwError('tail') : v._1; }
74 function last(xs) {
75 if (xs.ctor === 'Nil') { throwError('last'); }
76 var out = xs._0;
77 while (xs.ctor !== 'Nil') {
78 out = xs._0;
79 xs = xs._1;
80 }
81 return out;
82 }
84 function map(f, xs) {
85 var arr = [];
86 while (xs.ctor !== 'Nil') {
87 arr.push(f(xs._0));
88 xs = xs._1;
89 }
90 return fromArray(arr);
91 }
93 // f defined similarly for both foldl and foldr (NB: different from Haskell)
94 // ie, foldl :: (a -> b -> b) -> b -> [a] -> b
95 function foldl(f, b, xs) {
96 var acc = b;
97 while (xs.ctor !== 'Nil') {
98 acc = A2(f, xs._0, acc);
99 xs = xs._1;
100 }
101 return acc;
102 }
104 function foldr(f, b, xs) {
105 var arr = toArray(xs);
106 var acc = b;
107 for (var i = arr.length; i--; ) {
108 acc = A2(f, arr[i], acc);
109 }
110 return acc;
111 }
113 function foldl1(f, xs) {
114 return xs.ctor === 'Nil' ? throwError('foldl1') : foldl(f, xs._0, xs._1);
115 }
117 function foldr1(f, xs) {
118 if (xs.ctor === 'Nil') { throwError('foldr1'); }
119 var arr = toArray(xs);
120 var acc = arr.pop();
121 for (var i = arr.length; i--; ) {
122 acc = A2(f, arr[i], acc);
123 }
124 return acc;
125 }
127 function scanl(f, b, xs) {
128 var arr = toArray(xs);
129 arr.unshift(b);
130 var len = arr.length;
131 for (var i = 1; i < len; ++i) {
132 arr[i] = A2(f, arr[i], arr[i-1]);
133 }
134 return fromArray(arr);
135 }
137 function scanl1(f, xs) {
138 return xs.ctor === 'Nil' ? throwError('scanl1') : scanl(f, xs._0, xs._1);
139 }
141 function filter(pred, xs) {
142 var arr = [];
143 while (xs.ctor !== 'Nil') {
144 if (pred(xs._0)) { arr.push(xs._0); }
145 xs = xs._1;
146 }
147 return fromArray(arr);
148 }
150 function length(xs) {
151 var out = 0;
152 while (xs.ctor !== 'Nil') {
153 out += 1;
154 xs = xs._1;
155 }
156 return out;
157 }
159 function member(x, xs) {
160 while (xs.ctor !== 'Nil') {
161 if (Utils.eq(x,xs._0)) return true;
162 xs = xs._1;
163 }
164 return false;
165 }
167 function reverse(xs) { return fromArray(toArray(xs).reverse()); }
169 function concat(xss) {
170 if (xss.ctor === 'Nil') return xss;
171 var arr = toArray(xss);
172 var xs = arr[arr.length-1];
173 for (var i = arr.length-1; i--; ) {
174 xs = append(arr[i], xs);
175 }
176 return xs;
177 }
179 function all(pred, xs) {
180 while (xs.ctor !== 'Nil') {
181 if (!pred(xs._0)) return false;
182 xs = xs._1;
183 }
184 return true;
185 }
187 function any(pred, xs) {
188 while (xs.ctor !== 'Nil') {
189 if (pred(xs._0)) return true;
190 xs = xs._1;
191 }
192 return false;
193 }
195 function zipWith(f, xs, ys) {
196 var arr = [];
197 while (xs.ctor !== 'Nil' && ys.ctor !== 'Nil') {
198 arr.push(A2(f, xs._0, ys._0));
199 xs = xs._1;
200 ys = ys._1;
201 }
202 return fromArray(arr);
203 }
205 function zip(xs, ys) {
206 var arr = [];
207 while (xs.ctor !== 'Nil' && ys.ctor !== 'Nil') {
208 arr.push(Utils.Tuple2(xs._0, ys._0));
209 xs = xs._1;
210 ys = ys._1;
211 }
212 return fromArray(arr);
213 }
215 function sort(xs) {
216 function cmp(a,b) {
217 var ord = Utils.compare(a,b).ctor;
218 return ord=== 'EQ' ? 0 : ord === 'LT' ? -1 : 1;
219 }
220 return fromArray(toArray(xs).sort(cmp));
221 }
223 function take(n, xs) {
224 var arr = [];
225 while (xs.ctor !== 'Nil' && n > 0) {
226 arr.push(xs._0);
227 xs = xs._1;
228 --n;
229 }
230 return fromArray(arr);
231 }
233 function drop(n, xs) {
234 while (xs.ctor !== 'Nil' && n > 0) {
235 xs = xs._1;
236 --n;
237 }
238 return xs;
239 }
241 function join(sep, xss) {
242 if (typeof sep === 'string') return toArray(xss).join(sep);
243 if (xss.ctor === 'Nil') return Nil;
244 var s = toArray(sep);
245 var out = toArray(xss._0);
246 xss = xss._1;
247 while (xss.ctor !== 'Nil') {
248 out = out.concat(s, toArray(xss._0));
249 xss = xss._1;
250 }
251 return fromArray(out);
252 }
254 function split(sep, xs) {
255 var out = Nil;
256 var array = toArray(xs);
257 var s = toArray(sep);
258 var slen = s.length;
259 if (slen === 0) {
260 for (var i = array.length; i--; ) {
261 out = Cons(Cons(array[i],Nil), out);
262 }
263 return out;
264 }
265 var temp = Nil;
266 for (var i = array.length - slen; i >= 0; --i) {
267 var match = true;
268 for (var j = slen; j--; ) {
269 if (!Utils.eq(array[i+j], s[j])) { match = false; break; }
270 }
271 if (match) {
272 out = Cons(temp,out);
273 temp = Nil;
274 i -= slen - 1;
275 } else {
276 temp = Cons(array[i+j], temp);
277 }
278 }
279 for (var j = slen-1; j--; ) {
280 temp = Cons(array[j], temp);
281 }
282 out = Cons(temp, out);
283 return out;
284 }
286 Elm.Native.List.values = {
287 Nil:Nil,
288 Cons:Cons,
289 toArray:toArray,
290 fromArray:fromArray,
291 range:range,
292 append:append,
294 head:head,
295 tail:tail,
296 last:last,
298 map:F2(map),
299 foldl:F3(foldl),
300 foldr:F3(foldr),
302 foldl1:F2(foldl1),
303 foldr1:F2(foldr1),
304 scanl:F3(scanl),
305 scanl1:F2(scanl1),
306 filter:F2(filter),
307 length:length,
308 member:F2(member),
309 reverse:reverse,
310 concat:concat,
312 all:F2(all),
313 any:F2(any),
314 zipWith:F3(zipWith),
315 zip:F2(zip),
316 sort:sort,
317 take:F2(take),
318 drop:F2(drop),
320 join:F2(join),
321 split:F2(split)
322 };
323 return elm.Native.List = Elm.Native.List.values;
325};