git.iko.soy/elk
on 2ffacb7 help sign in
elk/libraries/Native/List.js
324 lines 8.3 kB history raw
1Elm.Native.List = {};
2Elm.Native.List.make = function(elm) {
3 elm.Native = elm.Native || {};
4 elm.Native.List = elm.Native.List || {};
5 if (elm.Native.List.values) return elm.Native.List.values;
6 if ('values' in Elm.Native.List)
7 return elm.Native.List.values = Elm.Native.List.values;
9 var Utils = Elm.Native.Utils.make(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 (xs.isText) return Utils.txt(xs.concat(ys));
57 if (typeof xs === "string") return xs.concat(ys);
58 if (xs.ctor === '[]') { return ys; }
59 var root = Cons(xs._0, Nil);
60 var curr = root;
61 xs = xs._1;
62 while (xs.ctor !== '[]') {
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 === '[]' ? throwError('head') : v._0; }
72 function tail(v) { return v.ctor === '[]' ? throwError('tail') : v._1; }
74 function last(xs) {
75 if (xs.ctor === '[]') { throwError('last'); }
76 var out = xs._0;
77 while (xs.ctor !== '[]') {
78 out = xs._0;
79 xs = xs._1;
80 }
81 return out;
82 }
84 function init(xs) {
85 if (xs.ctor === '[]') { throwError('init'); }
86 var root = Cons(xs._0, Nil);
87 var curr = root;
88 xs = xs._1;
89 while (xs._1.ctor !== '[]') {
90 curr._1 = Cons(xs._0, Nil)
91 xs = xs._1
92 curr = curr._1
93 }
94 return root;
95 }
97 function map(f, xs) {
98 var arr = [];
99 while (xs.ctor !== '[]') {
100 arr.push(f(xs._0));
101 xs = xs._1;
102 }
103 return fromArray(arr);
104 }
106 // f defined similarly for both foldl and foldr (NB: different from Haskell)
107 // ie, foldl : (a -> b -> b) -> b -> [a] -> b
108 function foldl(f, b, xs) {
109 var acc = b;
110 while (xs.ctor !== '[]') {
111 acc = A2(f, xs._0, acc);
112 xs = xs._1;
113 }
114 return acc;
115 }
117 function foldr(f, b, xs) {
118 var arr = toArray(xs);
119 var acc = b;
120 for (var i = arr.length; i--; ) {
121 acc = A2(f, arr[i], acc);
122 }
123 return acc;
124 }
126 function foldl1(f, xs) {
127 return xs.ctor === '[]' ? throwError('foldl1') : foldl(f, xs._0, xs._1);
128 }
130 function foldr1(f, xs) {
131 if (xs.ctor === '[]') { throwError('foldr1'); }
132 var arr = toArray(xs);
133 var acc = arr.pop();
134 for (var i = arr.length; i--; ) {
135 acc = A2(f, arr[i], acc);
136 }
137 return acc;
138 }
140 function scanl(f, b, xs) {
141 var arr = toArray(xs);
142 arr.unshift(b);
143 var len = arr.length;
144 for (var i = 1; i < len; ++i) {
145 arr[i] = A2(f, arr[i], arr[i-1]);
146 }
147 return fromArray(arr);
148 }
150 function scanl1(f, xs) {
151 return xs.ctor === '[]' ? throwError('scanl1') : scanl(f, xs._0, xs._1);
152 }
154 function filter(pred, xs) {
155 var arr = [];
156 while (xs.ctor !== '[]') {
157 if (pred(xs._0)) { arr.push(xs._0); }
158 xs = xs._1;
159 }
160 return fromArray(arr);
161 }
163 function length(xs) {
164 var out = 0;
165 while (xs.ctor !== '[]') {
166 out += 1;
167 xs = xs._1;
168 }
169 return out;
170 }
172 function member(x, xs) {
173 while (xs.ctor !== '[]') {
174 if (Utils.eq(x,xs._0)) return true;
175 xs = xs._1;
176 }
177 return false;
178 }
180 function reverse(xs) { return fromArray(toArray(xs).reverse()); }
182 function concat(xss) {
183 if (xss.ctor === '[]') return xss;
184 var arr = toArray(xss);
185 var xs = arr[arr.length-1];
186 for (var i = arr.length-1; i--; ) {
187 xs = append(arr[i], xs);
188 }
189 return xs;
190 }
192 function all(pred, xs) {
193 while (xs.ctor !== '[]') {
194 if (!pred(xs._0)) return false;
195 xs = xs._1;
196 }
197 return true;
198 }
200 function any(pred, xs) {
201 while (xs.ctor !== '[]') {
202 if (pred(xs._0)) return true;
203 xs = xs._1;
204 }
205 return false;
206 }
208 function zipWith(f, xs, ys) {
209 var arr = [];
210 while (xs.ctor !== '[]' && ys.ctor !== '[]') {
211 arr.push(A2(f, xs._0, ys._0));
212 xs = xs._1;
213 ys = ys._1;
214 }
215 return fromArray(arr);
216 }
218 function zip(xs, ys) {
219 var arr = [];
220 while (xs.ctor !== '[]' && ys.ctor !== '[]') {
221 arr.push(Utils.Tuple2(xs._0, ys._0));
222 xs = xs._1;
223 ys = ys._1;
224 }
225 return fromArray(arr);
226 }
228 function sort(xs) {
229 function cmp(a,b) {
230 var ord = Utils.compare(a,b).ctor;
231 return ord=== 'EQ' ? 0 : ord === 'LT' ? -1 : 1;
232 }
233 return fromArray(toArray(xs).sort(cmp));
234 }
236 function nth(xs, n) {
237 return toArray(xs)[n];
238 }
240 function take(n, xs) {
241 var arr = [];
242 while (xs.ctor !== '[]' && n > 0) {
243 arr.push(xs._0);
244 xs = xs._1;
245 --n;
246 }
247 return fromArray(arr);
248 }
250 function drop(n, xs) {
251 while (xs.ctor !== '[]' && n > 0) {
252 xs = xs._1;
253 --n;
254 }
255 return xs;
256 }
258 function repeat(n, x) {
259 var arr = [];
260 var pattern = [x];
261 while (n > 0) {
262 if (n & 1) arr = arr.concat(pattern);
263 n >>= 1, pattern = pattern.concat(pattern);
264 }
265 return fromArray(arr);
266 }
268 function join(sep, xss) {
269 if (sep.isText) return Utils.txt(toArray(xss).join(sep));
270 if (typeof sep === 'string') return toArray(xss).join(sep);
271 if (xss.ctor === '[]') return Nil;
272 var s = toArray(sep);
273 var out = toArray(xss._0);
274 xss = xss._1;
275 while (xss.ctor !== '[]') {
276 out = out.concat(s, toArray(xss._0));
277 xss = xss._1;
278 }
279 return fromArray(out);
280 }
282 Elm.Native.List.values = {
283 Nil:Nil,
284 Cons:Cons,
285 cons:F2(Cons),
286 toArray:toArray,
287 fromArray:fromArray,
288 range:range,
289 append:append,
291 head:head,
292 tail:tail,
293 last:last,
294 init:init,
296 map:F2(map),
297 foldl:F3(foldl),
298 foldr:F3(foldr),
300 foldl1:F2(foldl1),
301 foldr1:F2(foldr1),
302 scanl:F3(scanl),
303 scanl1:F2(scanl1),
304 filter:F2(filter),
305 length:length,
306 member:F2(member),
307 reverse:reverse,
308 concat:concat,
310 all:F2(all),
311 any:F2(any),
312 zipWith:F3(zipWith),
313 zip:F2(zip),
314 sort:sort,
315 nth:F2(nth),
316 take:F2(take),
317 drop:F2(drop),
318 repeat:F2(repeat),
320 join:F2(join)
321 };
322 return elm.Native.List.values = Elm.Native.List.values;
324};