1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
type List[A] is (Cons[A] | Nil[A])
"""
A persistent list with functional transformations.

## Usage

```pony
use "collections/persistent"

actor Main
  new create(env: Env) =>
    try
      let l1 = Lists[U32]([2; 4; 6; 8]) // List(2, 4, 6, 8)

      let empty = Lists[U32].empty() // List()

      // prepend() returns a new List, leaving the
      // old list unchanged
      let l2 = empty.prepend(3) // List(3)
      let l3 = l2.prepend(2) // List(2, 3)
      let l4 = l3.prepend(1) // List(1, 2, 3)
      let l4_head = l4.head() // 1
      let l4_tail = l4.tail() // List(2, 3)

      l4_head == 1
      Lists[U32].eq(l4, Lists[U32]([1; 2; 3]))?
      Lists[U32].eq(l4_tail, Lists[U32]([2; 3]))?

      let doubled = l4.map[U32]({(x) => x * 2 })

      Lists[U32].eq(doubled, Lists[U32]([2; 4; 6]))?
    end
```
"""

primitive Lists[A]
  """
  A primitive containing helper functions for constructing and
  testing Lists.
  """

  fun empty(): List[A] =>
    """
    Returns an empty list.
    """
    Nil[A]

  fun cons(h: val->A, t: List[A]): List[A] =>
    """
    Returns a list that has h as a head and t as a tail.
    """
    Cons[A](h, t)

  fun apply(arr: Array[val->A]): List[A] =>
    """
    Builds a new list from an Array
    """
    this.from(arr.values())

  fun from(iter: Iterator[val->A]): List[A] =>
    """
    Builds a new list from an iterator
    """
    var l: List[A] = Nil[A]

    for i in iter do
      l = Cons[A](i, l)
    end
    l.reverse()

  fun eq[T: Equatable[T] val = A](l1: List[T], l2: List[T]): Bool ? =>
    """
    Checks whether two lists are equal.
    """
    if (l1.is_empty() and l2.is_empty()) then
      true
    elseif (l1.is_empty() and l2.is_non_empty()) then
      false
    elseif (l1.is_non_empty() and l2.is_empty()) then
      false
    elseif (l1.head()? != l2.head()?) then
      false
    else
      eq[T](l1.tail()?, l2.tail()?)?
    end

primitive Nil[A] is ReadSeq[val->A]
  """
  The empty list of As.
  """

  fun size(): USize =>
    """
    Returns the size of the list.
    """
    0

  fun apply(i: USize): val->A ? =>
    """
    Returns the i-th element of the sequence. For the empty list this call will
    always error because any index will be out of bounds.
    """
    error

  fun values(): Iterator[val->A]^ =>
    """
    Returns an empty iterator over the elements of the empty list.
    """
    object ref is Iterator[val->A]
      fun has_next(): Bool => false
      fun ref next(): val->A! ? => error
    end

  fun is_empty(): Bool =>
    """
    Returns a Bool indicating if the list is empty.
    """
    true

  fun is_non_empty(): Bool =>
    """
    Returns a Bool indicating if the list is non-empty.
    """
    false

  fun head(): val->A ? =>
    """
    Returns an error, since Nil has no head.
    """
    error

  fun tail(): List[A] ? =>
    """
    Returns an error, since Nil has no tail.
    """
    error

  fun reverse(): Nil[A] =>
    """
    The reverse of the empty list is the empty list.
    """
    this

  fun prepend(a: val->A!): Cons[A] =>
    """
    Builds a new list with an element added to the front of this list.
    """
    Cons[A](consume a, this)

  fun concat(l: List[A]): List[A] =>
    """
    The concatenation of any list l with the empty list is l.
    """
    l

  fun map[B](f: {(val->A): val->B} box): Nil[B] =>
    """
    Mapping a function from A to B over the empty list yields the
    empty list of Bs.
    """
    Nil[B]

  fun flat_map[B](f: {(val->A): List[B]} box): Nil[B] =>
    """
    Flatmapping a function from A to B over the empty list yields the
    empty list of Bs.
    """
    Nil[B]

  fun for_each(f: {(val->A)} box) =>
    """
    Applying a function to every member of the empty list is a no-op.
    """
    None

  fun filter(f: {(val->A): Bool} box): Nil[A] =>
    """
    Filtering the empty list yields the empty list.
    """
    this

  fun fold[B](f: {(B, val->A): B^} box, acc: B): B =>
    """
    Folding over the empty list yields the initial accumulator.
    """
    consume acc

  fun every(f: {(val->A): Bool} box): Bool =>
    """
    Any predicate is true of every member of the empty list.
    """
    true

  fun exists(f: {(val->A): Bool} box): Bool =>
    """
    For any predicate, there is no element that satisfies it in the empty
    list.
    """
    false

  fun partition(f: {(val->A): Bool} box): (Nil[A], Nil[A]) =>
    """
    The only partition of the empty list is two empty lists.
    """
    (this, this)

  fun drop(n: USize): Nil[A] =>
    """
    There are no elements to drop from the empty list.
    """
    this

  fun drop_while(f: {(val->A): Bool} box): Nil[A] =>
    """
    There are no elements to drop from the empty list.
    """
    this

  fun take(n: USize): Nil[A] =>
    """
    There are no elements to take from the empty list.
    """
    this

  fun take_while(f: {(val->A): Bool} box): Nil[A] =>
    """
    There are no elements to take from the empty list.
    """
    this

  fun val contains[T: (A & HasEq[A!] #read) = A](a: val->T): Bool =>
    false

class val Cons[A] is ReadSeq[val->A]
  """
  A list with a head and a tail, where the tail can be empty.
  """

  let _size: USize
  let _head: val->A
  let _tail: List[A] val

  new val create(a: val->A, t: List[A]) =>
    _head = consume a
    _tail = consume t
    _size = 1 + _tail.size()

  fun size(): USize =>
    """
    Returns the size of the list.
    """
    _size

  fun apply(i: USize): val->A ? =>
    """
    Returns the i-th element of the list. Errors if the index is out of bounds.
    """
    match i
    | 0 => _head
    else _tail(i - 1)?
    end

  fun values(): Iterator[val->A]^ =>
    """
    Returns an iterator over the elements of the list.
    """
    object is Iterator[val->A]
      var _list: List[A] box = this
      fun has_next(): Bool => _list isnt Nil[A]
      fun ref next(): val->A! ? => (_list = _list.tail()?).head()?
    end

  fun is_empty(): Bool =>
    """
    Returns a Bool indicating if the list is empty.
    """
    false

  fun is_non_empty(): Bool =>
    """
    Returns a Bool indicating if the list is non-empty.
    """
    true

  fun head(): val->A =>
    """
    Returns the head of the list.
    """
    _head

  fun tail(): List[A] =>
    """
    Returns the tail of the list.
    """
    _tail

  fun val reverse(): List[A] =>
    """
    Builds a new list by reversing the elements in the list.
    """
    _reverse(this, Nil[A])

  fun val _reverse(l: List[A], acc: List[A]): List[A] =>
    """
    Private helper for reverse, recursively working on elements.
    """
    match l
    | let cons: Cons[A] => _reverse(cons.tail(), acc.prepend(cons.head()))
    else
      acc
    end

  fun val prepend(a: val->A!): Cons[A] =>
    """
    Builds a new list with an element added to the front of this list.
    """
    Cons[A](consume a, this)

  fun val concat(l: List[A]): List[A] =>
    """
    Builds a new list that is the concatenation of this list and the provided
    list.
    """
    _concat(l, this.reverse())

  fun val _concat(l: List[A], acc: List[A]): List[A] =>
    """
    Private helper for concat that recursively builds the new list.
    """
    match l
    | let cons: Cons[A] => _concat(cons.tail(), acc.prepend(cons.head()))
    else
      acc.reverse()
    end

  fun val map[B](f: {(val->A): val->B} box): List[B] =>
    """
    Builds a new list by applying a function to every member of the list.
    """
    _map[B](this, f, Nil[B])

  fun _map[B](l: List[A], f: {(val->A): val->B} box, acc: List[B]): List[B] =>
    """
    Private helper for map, recursively applying function to elements.
    """
    match l
    | let cons: Cons[A] =>
      _map[B](cons.tail(), f, acc.prepend(f(cons.head())))
    else
      acc.reverse()
    end

  fun val flat_map[B](f: {(val->A): List[B]} box): List[B] =>
    """
    Builds a new list by applying a function to every member of the list and
    using the elements of the resulting lists.
    """
    _flat_map[B](this, f, Nil[B])

  fun _flat_map[B](l: List[A], f: {(val->A): List[B]} box, acc: List[B]):
  List[B] =>
    """
    Private helper for flat_map, recursively working on elements.
    """
    match l
    | let cons: Cons[A] =>
      _flat_map[B](cons.tail(), f, _rev_prepend[B](f(cons.head()), acc))
    else
      acc.reverse()
    end

  fun tag _rev_prepend[B](l: List[B], target: List[B]): List[B] =>
    """
    Prepends l in reverse order onto target
    """
    match l
    | let cns: Cons[B] =>
      _rev_prepend[B](cns.tail(), target.prepend(cns.head()))
    else
      target
    end

  fun val for_each(f: {(val->A)} box) =>
    """
    Applies the supplied function to every element of the list in order.
    """
    _for_each(this, f)

  fun _for_each(l: List[A], f: {(val->A)} box) =>
    """
    Private helper for for_each, recursively working on elements.
    """
    match l
    | let cons: Cons[A] =>
      f(cons.head())
      _for_each(cons.tail(), f)
    end

  fun val filter(f: {(val->A): Bool} box): List[A] =>
    """
    Builds a new list with those elements that satisfy a provided predicate.
    """
    _filter(this, f, Nil[A])

  fun _filter(l: List[A], f: {(val->A): Bool} box, acc: List[A]): List[A] =>
    """
    Private helper for filter, recursively working on elements, keeping those
    that match the predicate and discarding those that don't.
    """
    match l
    | let cons: Cons[A] =>
      if (f(cons.head())) then
        _filter(cons.tail(), f, acc.prepend(cons.head()))
      else
        _filter(cons.tail(), f, acc)
      end
    else
      acc.reverse()
    end

  fun val fold[B](f: {(B, val->A): B^} box, acc: B): B =>
    """
    Folds the elements of the list using the supplied function.
    """
    _fold[B](this, f, consume acc)

  fun val _fold[B](l: List[A], f: {(B, val->A): B^} box, acc: B): B =>
    """
    Private helper for fold, recursively working on elements.
    """
    match l
    | let cons: Cons[A] =>
      _fold[B](cons.tail(), f, f(consume acc, cons.head()))
    else
      acc
    end

  fun val every(f: {(val->A): Bool} box): Bool =>
    """
    Returns true if every element satisfies the provided predicate, false
    otherwise.
    """
    _every(this, f)

  fun _every(l: List[A], f: {(val->A): Bool} box): Bool =>
    """
    Private helper for every, recursively testing predicate on elements,
    returning false immediately on an element that fails to satisfy the
    predicate.
    """
    match l
    | let cons: Cons[A] =>
      if (f(cons.head())) then
        _every(cons.tail(), f)
      else
        false
      end
    else
      true
    end

  fun val exists(f: {(val->A): Bool} box): Bool =>
    """
    Returns true if at least one element satisfies the provided predicate,
    false otherwise.
    """
    _exists(this, f)

  fun _exists(l: List[A], f: {(val->A): Bool} box): Bool =>
    """
    Private helper for exists, recursively testing predicate on elements,
    returning true immediately on an element satisfying the predicate.
    """
    match l
    | let cons: Cons[A] =>
      if (f(cons.head())) then
        true
      else
        _exists(cons.tail(), f)
      end
    else
      false
    end

  fun val partition(f: {(val->A): Bool} box): (List[A], List[A]) =>
    """
    Builds a pair of lists, the first of which is made up of the elements
    satisfying the supplied predicate and the second of which is made up of
    those that do not.
    """
    var hits: List[A] = Nil[A]
    var misses: List[A] = Nil[A]
    var cur: List[A] = this
    while true do
      match cur
      | let cons: Cons[A] =>
        let next = cons.head()
        if f(next) then
          hits = hits.prepend(next)
        else
          misses = misses.prepend(next)
        end
        cur = cons.tail()
      else
        break
      end
    end
    (hits.reverse(), misses.reverse())

  fun val drop(n: USize): List[A] =>
    """
    Builds a list by dropping the first n elements.
    """
    var cur: List[A] = this
    if cur.size() <= n then return Nil[A] end
    var count = n
    while count > 0 do
      match cur
      | let cons: Cons[A] =>
        cur = cons.tail()
        count = count - 1
      end
    end
    cur

  fun val drop_while(f: {(val->A): Bool} box): List[A] =>
    """
    Builds a list by dropping elements from the front of the list until one
    fails to satisfy the provided predicate.
    """
    var cur: List[A] = this
    while true do
      match cur
      | let cons: Cons[A] =>
        if f(cons.head()) then cur = cons.tail() else break end
      else
        return Nil[A]
      end
    end
    cur

  fun val take(n: USize): List[A] =>
    """
    Builds a list of the first n elements.
    """
    var cur: List[A] = this
    if cur.size() <= n then return cur end
    var count = n
    var res: List[A] = Nil[A]
    while count > 0 do
      match cur
      | let cons: Cons[A] =>
        res = res.prepend(cons.head())
        cur = cons.tail()
      else
        return res.reverse()
      end
      count = count - 1
    end
    res.reverse()

  fun val take_while(f: {(val->A): Bool} box): List[A] =>
    """
    Builds a list of elements satisfying the provided predicate until one does
    not.
    """
    var cur: List[A] = this
    var res: List[A] = Nil[A]
    while true do
      match cur
      | let cons: Cons[A] =>
        if f(cons.head()) then
          res = res.prepend(cons.head())
          cur = cons.tail()
        else
          break
        end
      else
        return res.reverse()
      end
    end
    res.reverse()