sourcelibs/Lists/src/Lists.xtl
1⍝# Lists: list functions -- differences, windows, moving means, run
2⍝# lengths, chunks, shifts, interleaving, binary search, raze.
3⍝# Import it with an alias of your choice: "q:" u_se< "Lists".
4⍝# Put libs/Lists/src on XETAL_PATH ("just path"); the reference is libs/Lists/docs.
5⍝# Names with l: are exported; those under h: are private to this file.
6⍝#
7⍝# Counts and sizes go on the left, the list on the right, as for the
8⍝# built-ins: 3 q:w_indows v.
9
10⍝## Differences and windows
11
12⍝# d_eltas v: each item minus the one before (one fewer item).
13ˡd̲eltas ← { v → (1 d̲rop v) − -1 d̲rop v }
14
15⍝# n w_indows v: every run of n consecutive items, one per row.
16ˡw̲indows ← { n v →
17 n < 1 ? @ p̲anic< "a window holds 1 item or more, not {n}"
18 k ← 1 + (t̲ally v) − n
19 k < 1 ? (0 c̲at n) r̲eshape v
20 ((r̲ange k) '+ t̲able o̲ffsets n) s̲elect v
21}
22
23⍝# n m_ovingMean v: the mean of each window of n (a Float each).
24ˡm̲ovingMean ← { n v → (f̲loat '+ r̲/₂ n ˡw̲indows v) ÷ f̲loat n }
25
26⍝## Runs
27
28⍝# Where each run of equal items starts (a 0/1 mask).
29ʰs̲tarts ← { v → 0 = t̲ally v ? 0 r̲eshape 1 = 1◆ 1 c̲at (1 d̲rop v) ≠ -1 d̲rop v }
30
31⍝# r_unValues v: the item of each run of equal items ("aaabcc" is "abc").
32ˡr̲unValues ← { v → (ʰs̲tarts v) r̲eplicate v }
33
34⍝# r_unLengths v: the length of each run ("aaabcc" is 3 1 2).
35ˡr̲unLengths ← { v → ˡd̲eltas (w̲here ʰs̲tarts v) c̲at 1 + t̲ally v }
36
37⍝## Reshaping
38
39⍝# n c_hunks v: v cut into pieces of n (the last may be shorter), as a list.
40ˡc̲hunks ← { n v →
41 n < 1 ? @ p̲anic< "a chunk holds 1 item or more, not {n}"
42 (1 + (o̲ffsets t̲ally v) d̲iv n) p̲artition v
43}
44
45⍝# r_aze list: the items of a list of lists joined into one list (APL2's
46⍝# enlist of a simple list). An empty list has no items to take a type's
47⍝# fill from: error[no-identity].
48ˡr̲aze ← { b →
49 0 = t̲ally b ? @ p̲anic< "r_aze needs at least one list: an empty list has no items to join (nor a type to make an empty result of)"
50 d̲isclose '{ e̲nclose (d̲isclose ⍺) c̲at d̲isclose ⍵ } r̲/ b
51}
52
53⍝# n s_hift v: v moved n places toward the front (back for negative n),
54⍝# without wrapping: the places left empty get the fill (0, or a space).
55ˡs̲hift ← { n v → t ← t̲ally v◆ n ≥ 0 ? t t̲ake n d̲rop v◆ (n̲eg t) t̲ake n d̲rop v }
56
57⍝# a i_nterleave b: a1 b1 a2 b2 ... (a and b of one length).
58ˡi̲nterleave ← { a b → r̲avel₂ (2 c̲at t̲ally a) r̲eshape a c̲at b }
59
60⍝## Searching
61
62⍝# Binary search in sorted v between lo and hi: how many items are <= x.
63ʰb̲s ← { v x lo hi →
64 lo ≥ hi ? lo
65 m ← (lo + hi + 1) d̲iv 2
66 (f̲irst m s̲elect v) ≤ x ? (((v ʰb̲s x)_ m)_ hi)
67 ((v ʰb̲s x)_ lo)_ m − 1
68}
69
70⍝# v b_search x: in a sorted list v, how many items are <= each item of
71⍝# x: the place x would go after its equals (dfns bsearch).
72ˡb̲search ← { v x → '{ y → (((v ʰb̲s y)_ 0)_ t̲ally v) } e̲ach x }
p̲anic< expands to
(⎕P̲ANIC ("r_aze needs at least one list: an empty list has no items to join (nor a type to make an empty result of)"))