initial commit

21 files changed, 455 insertions, 0 deletions

diff --git a/p99/p01.neb b/p99/p01.neb
new file mode 100644
index 0000000..e50cfe7
--- /dev/null
+++ b/p99/p01.neb
@@ -0,0 +1,5 @@
+; P01 Find the last box of a list.
+
+(def a (list "a" "b" "c" "d"))
+
+(print (last a))
diff --git a/p99/p02.neb b/p99/p02.neb
new file mode 100644
index 0000000..317674e
--- /dev/null
+++ b/p99/p02.neb
@@ -0,0 +1,8 @@
+; P02 - Find the last two elements of a list.
+
+(def a (list "a" "b" "c" "d"))
+
+; slice takes the index (1-based) to begin
+; and, optionally, the length of the slice
+; (when missing, will grab until the end)
+(print (->string (slice a (- (length a) 1))))
diff --git a/p99/p03.neb b/p99/p03.neb
new file mode 100644
index 0000000..05e0457
--- /dev/null
+++ b/p99/p03.neb
@@ -0,0 +1,10 @@
+; P03 - Find the K'th element of a list. 
+; The first element in the list is number 1.
+
+(def a (list "a" "b" "c" "d"))
+
+(func kth (lst k)
+    (first (slice lst k 1)))  ; since slice returns a list, get the element with first
+
+(print (kth a 3))
+;(kth a 8)  ; panic! there is no 8th element
diff --git a/p99/p04.neb b/p99/p04.neb
new file mode 100644
index 0000000..544dc00
--- /dev/null
+++ b/p99/p04.neb
@@ -0,0 +1,5 @@
+; P04 - Find the number of elements of a list
+
+(def a (list "a" "b" "c" "d"))
+
+(print (->string (length a)))
diff --git a/p99/p05.neb b/p99/p05.neb
new file mode 100644
index 0000000..b04e329
--- /dev/null
+++ b/p99/p05.neb
@@ -0,0 +1,5 @@
+; P05 - Reverse a list
+
+(def a (list "a" "b" "c" "d"))
+
+(print (->string (reverse a)))
diff --git a/p99/p06.neb b/p99/p06.neb
new file mode 100644
index 0000000..f219058
--- /dev/null
+++ b/p99/p06.neb
@@ -0,0 +1,23 @@
+; P06 Find out whether a list is a palindrome.
+; A palindrome can be read forward or backward; e.g. (x a m a x).
+
+(def odd-good (list "x" "a" "m" "a" "x")) ; odd number of elements (good)
+(def odd-bad (list "x" "f" "m" "a" "x")) ; odd number of elements (bad)
+(def even-good (list "a" "b" "b" "a")) ; even number of elements (good)
+(def even-bad (list "a" "b" "b" "f")) ; even number of elements (bad)
+(def single (list "a")) ; single element
+(def empty (list))
+
+(func palindrome? (lst)  ; by convention, funcs returning :bool end with a ?
+    (if (< (length lst) 2)  ; 0 or 1 element lists are palindromic
+        #true
+        (and
+            (eq? (first lst) (last lst))  ; first element and last element are equal
+            (palindrome? (most (rest lst))))))  ; this would be clearer if slices supported negative numbers
+
+(print (->string (palindrome? odd-good)))
+(print (->string (palindrome? odd-bad)))
+(print (->string (palindrome? even-good)))
+(print (->string (palindrome? even-bad)))
+(print (->string (palindrome? single)))
+(print (->string (palindrome? empty)))
diff --git a/p99/p07.neb b/p99/p07.neb
new file mode 100644
index 0000000..9eee9ef
--- /dev/null
+++ b/p99/p07.neb
@@ -0,0 +1,57 @@
+; P07 Flatten a nested array structure.
+; Transform an array, possibly holding arrays as elements into a `flat'
+; list by replacing each array with its elements (recursively).
+
+(def a (list "a" (list "b" (list "c" "d") "e")))
+
+; this belongs in stdlib
+(func extend (lst1 lst2)
+    (reduce append lst2 lst1))
+
+; can overload functions of different arities
+(func flatten-iter (item)
+    (flatten-iter item (list)))
+
+; iterative solution
+(func flatten-iter (item acc)
+    (branch
+        ((eq? (typeof item) :[:any])
+            (if (empty? item)
+                    acc
+                (flatten-iter (rest item) (extend acc (flatten-iter (first item))))))
+        (#true
+            (append acc item))))
+
+; we can also use the type system/dynamic dispatch to split up the work
+(func flatten-typ (item)
+    (flatten-typ item (list)))
+
+; non-empty lists
+(func flatten-typ (lst :{:any} acc)
+    (flatten-typ (rest lst) (extend acc (flatten-typ (first lst)))))
+
+; empty lists
+(func flatten-typ (lst :nil acc)
+    acc)
+
+; other things
+; note: we would need to know what type(s) is inside the list to avoid an
+; ambiguous definition
+;(func flatten-typ (item :string acc)
+;    (append acc item))
+
+; this might be clearer/more flexible
+; maybe "not this type" should be a thing, like :![:any]
+(func not-a-list? (item)
+    (not (eq? (typeof item) :[:any])))
+
+(type :not-a-list :any not-a-list?) ; should be able to pass a lambda
+
+; this handles anything that's not a list
+(func flatten-typ (item :not-a-list acc)
+    (append acc item))
+
+(print (->string a))
+(print (->string (flatten-iter a)))
+(print (->string a))
+(print (->string (flatten-typ a)))
diff --git a/p99/p08.neb b/p99/p08.neb
new file mode 100644
index 0000000..5df816f
--- /dev/null
+++ b/p99/p08.neb
@@ -0,0 +1,57 @@
+; P08 Eliminate consecutive duplicates of list elements.
+; If a list contains repeated elements they should be replaced with a
+; single copy of the element. The order of the elements should not be changed.
+
+(def a (list "a" "a" "a" "a" "b" "c" "c" "a" "a" "d" "e" "e" "e" "e"))
+
+(func compress-iter (lst)
+    (def out (list))
+    (for-each lst
+        (if (or (empty? out) 
+                (not (eq? _item_ (last out))))
+            (redef out (append out _item_))))
+    out)
+
+; use the type system/dynamic dispatch
+(func compress-typ (lst)
+    (compress-typ lst (list)))
+
+; empty lists
+(func compress-typ (lst :nil acc)
+    acc)
+
+; non-empty lists, combined with a branch
+;(func compress-typ (lst :{:any} acc)
+;    (branch
+;        ((empty? acc) (compress-typ (rest lst) (list (first lst))))
+;        ((not (eq? (first lst) (last acc))) (compress-typ (rest lst) (append acc (first lst))))
+;        (#true (compress-typ (rest lst) acc))))
+
+; non-empty lists, non-empty accumulator
+(func compress-typ (lst :{:any} acc :{:any})
+    (if (eq? (first lst) (last acc)) 
+        (compress-typ (rest lst) acc)  ; don't append
+        (compress-typ (rest lst) (append acc (first lst)))))
+
+; non-empty lists, empty accumulator
+(func compress-typ (lst :{:any} acc :nil)
+    (compress-typ (rest lst) (list (first lst))))
+
+;(func extend (lst1 lst2)
+;    (reduce append lst2 lst1))
+
+; everything is an expression, so you could do this too
+; not sure if you'd want to, though, as you're creating
+; a list and then immediately killing it, which seems
+; like it's probably wasteful in the interpreter
+;(func compress-typ (lst :{:any} acc :{:any})
+;    (compress-typ (rest lst)
+;        (extend
+;            acc
+;            (if (not (eq? (first lst) (last acc)))
+;                (list (first lst))))))
+                
+
+(print (->string a))
+(print (->string (compress-iter a)))
+(print (->string (compress-typ a)))
diff --git a/p99/p09.neb b/p99/p09.neb
new file mode 100644
index 0000000..619c4a4
--- /dev/null
+++ b/p99/p09.neb
@@ -0,0 +1,31 @@
+; P09 Pack consecutive duplicates of list elements into sublists.
+; If a list contains repeated elements they should be placed in separate sublists.
+
+(def a (list "a" "a" "a" "a" "b" "c" "c" "a" "a" "d" "e" "e" "e" "e"))
+
+; the list, the most recent value, the accumulator
+(func pack-dup (lst)
+    (pack-dup lst "" (list)))
+
+(func pack-dup (lst prev acc)
+    (branch
+        ((empty? lst) acc) ; if we're done, return acc
+        ((eq? (first lst) prev) ; the item is the same as the previous item
+            (pack-dup 
+                (rest lst) 
+                prev 
+                (append  ; add item to the last list in acc
+                    (most acc) 
+                    (append 
+                        (last acc) 
+                        prev))))
+        (#true
+            (pack-dup 
+                (rest lst) 
+                (first lst) 
+                (append 
+                    acc 
+                    (list (first lst)))))))  ; add new list with this item
+
+(print (->string a))
+(print (->string (pack-dup a)))
diff --git a/p99/p10.neb b/p99/p10.neb
new file mode 100644
index 0000000..25ea1dc
--- /dev/null
+++ b/p99/p10.neb
@@ -0,0 +1,15 @@
+; P10 Run-length encoding of a list.
+; Use the result of problem P09 to implement the so-called run-length
+; encoding data compression method. Consecutive duplicates of elements
+; are encoded as arrays [N, E] where N is the number of duplicates of the
+; element E.
+
+(use "p09.neb")  ; NOTE: this runs everything at this juncture, not just def/func
+
+(func encode (lst)
+    (map
+        (lambda (item)
+            (list (length item) (first item)))
+        lst))
+
+(print (->string (encode (pack-dup a))))
diff --git a/p99/p11.neb b/p99/p11.neb
new file mode 100644
index 0000000..546a7c2
--- /dev/null
+++ b/p99/p11.neb
@@ -0,0 +1,25 @@
+; P11 (*) Modified run-length encoding.
+; Modify the result of problem P10 in such a way that if an element has
+; no duplicates it is simply copied into the result list. Only elements
+; with duplicates are transferred as (N E) lists.
+
+(use "p10.neb")
+
+(func encode-modified (lst)
+    (map
+        (lambda (item)
+            (if (eq? 1 (length item))
+                (first item)
+                (list (length item) (first item))))
+        lst))
+
+(func encode-squish (lst)
+    (map
+        (lambda (item)
+            (if (eq? 1 (first item))
+                (last item)
+                item))
+        lst))
+
+(print (concat "from result of P09: " (->string (encode-modified (pack-dup a)))))
+(print (concat "from result of P10: " (->string (encode-squish (encode (pack-dup a))))))
diff --git a/p99/p12.neb b/p99/p12.neb
new file mode 100644
index 0000000..7d8ec4e
--- /dev/null
+++ b/p99/p12.neb
@@ -0,0 +1,37 @@
+; P12 Decode a run-length encoded list.
+; Given a run-length code list generated as specified in problem P11.
+; Construct its uncompressed version.
+
+(def a (list (list 4 "a") "b" (list 2 "c") (list 2 "a") "d" (list 4 "e")))
+
+(func extend (lst1 lst2)
+    (reduce append lst2 lst1))
+
+(func flatten (lst)
+    (reduce
+        (lambda (x y) (extend x y))
+        lst
+        (list)))
+
+(func decode (lst)
+    (flatten
+        (map
+            (lambda (item)
+                (if (eq? 1 (length item)) 
+                    (list item) 
+                    (rpt (first item) (last item)))) 
+            lst)))
+            
+(func rpt (cnt let)
+    (if (eq? cnt 1)
+        (list let)
+        (extend (list let) (rpt (- cnt 1) let))))
+
+; iterative
+(func rpt-iter (cnt let)
+    (def out (list))
+    (for-count cnt
+        (redef out (append out let)))
+    out)
+
+(print (->string (decode a)))
diff --git a/p99/p13.neb b/p99/p13.neb
new file mode 100644
index 0000000..e32d8cb
--- /dev/null
+++ b/p99/p13.neb
@@ -0,0 +1,30 @@
+; P13 Run-length encoding of a list (direct solution).
+; Implement the so-called run-length encoding data compression method directly. 
+; I.e. don't explicitly create the sublists containing the duplicates, as in problem P09, 
+; but only count them. As in problem P11, simplify the result list by replacing the 
+; singleton lists (1 X) by X.
+
+(def a (list "a" "a" "a" "a" "b" "c" "c" "a" "a" "d" "e" "e" "e" "e"))
+
+(func encode-direct (lst)
+    (encode-direct lst "" (list)))
+
+(func encode-direct (lst :nil prev acc)
+    acc)
+
+(func encode-direct (lst :{:any} prev acc)
+    (if (eq? (first lst) prev)
+        (encode-direct
+            (rest lst)
+            prev
+            (append (most acc)
+                (if (list? (last acc))
+                    (list (+ 1 (first (last acc))) prev)
+                    (list 2 prev))))
+        (encode-direct
+            (rest lst)
+            (first lst)
+            (append acc (first lst)))))
+
+(print (->string a))
+(print (->string (encode-direct a)))
diff --git a/p99/p14.neb b/p99/p14.neb
new file mode 100644
index 0000000..5af9fc0
--- /dev/null
+++ b/p99/p14.neb
@@ -0,0 +1,15 @@
+; P14: Duplicate the elements of a list.
+
+(def a (list "a" "b" "c" "c" "d"))
+
+(func dup (lst)
+    (reduce
+        (lambda (acc item)
+            (append
+                (append acc item)
+                item))
+        lst
+        (list)))
+
+(print (->string a))
+(print (->string (dup a)))
diff --git a/p99/p15.neb b/p99/p15.neb
new file mode 100644
index 0000000..12fa8cb
--- /dev/null
+++ b/p99/p15.neb
@@ -0,0 +1,17 @@
+; P15 Replicate the elements of a list a given number of times.
+
+(def a (list "a" "b" "c"))
+
+(func repli (lst cnt)
+    (reduce
+        (lambda (acc item)
+            (def out acc)
+            (for-count cnt
+                (redef out
+                    (append out item)))
+            out)
+            lst
+            (list)))
+
+(print (->string a))
+(print (->string (repli a 3)))
diff --git a/p99/p16.neb b/p99/p16.neb
new file mode 100644
index 0000000..e8fc459
--- /dev/null
+++ b/p99/p16.neb
@@ -0,0 +1,19 @@
+; P16 Drop every N'th element from a list.
+
+(def a (list "a" "b" "c" "d" "e" "f" "g" "h" "i" "k"))
+
+(func drop-n (lst n)
+    (drop-n lst n (list) n))
+
+(func drop-n (lst :nil n acc idx)
+    acc)
+
+(func drop-n (lst :{:any} n acc idx)
+    (if (eq? 1 idx)
+        (drop-n (rest lst) n acc n)  ; reset n, don't add to acc
+        (drop-n (rest lst) n (append acc (first lst)) (-- idx))))
+
+(func -- (num) (- num 1))
+
+(print (->string a))
+(print (->string (drop-n a 3)))
diff --git a/p99/p17.neb b/p99/p17.neb
new file mode 100644
index 0000000..d586e87
--- /dev/null
+++ b/p99/p17.neb
@@ -0,0 +1,17 @@
+; P17 Split a list into two parts; the length of the first part is given.
+; Do not use any predefined functions.
+
+(def a (list "a" "b" "c" "d" "e" "f" "g" "h" "i" "k"))
+
+(func spl (lst idx)
+    (spl lst idx (list)))
+
+(func spl (lst idx acc)
+    (if (eq? idx 0)
+        (list acc lst)
+        (spl (rest lst) (-- idx) (append acc (first lst)))))
+
+(func -- (num) (- num 1))
+
+(print (->string a))
+(print (->string (spl a 3)))
diff --git a/p99/p18.neb b/p99/p18.neb
new file mode 100644
index 0000000..7ccf0b7
--- /dev/null
+++ b/p99/p18.neb
@@ -0,0 +1,27 @@
+; P18 Extract a slice from a list.
+; Given two indices, I and K, the slice is the list containing the elements between the 
+; I'th and K'th element of the original list (both limits included). Start counting the elements with 1.
+
+(def a (list "a" "b" "c" "d" "e" "f" "g" "h" "i" "k"))
+
+(func my-slice (lst idx1 idx2)
+    (my-slice lst idx1 idx2 (list)))
+
+(func my-slice (lst :nil idx1 idx2 acc) acc)
+
+(func my-slice (lst :{:any} idx1 idx2 acc)
+    (my-slice 
+        (rest lst) 
+        (-- idx1) 
+        (-- idx2) 
+        (if
+            (or
+                (> idx1 1)
+                (< idx2 1))
+            acc
+            (append acc (first lst)))))
+
+(func -- (num) (- num 1))
+
+(print (->string a))
+(print (->string (my-slice a 3 7)))
diff --git a/p99/p19.neb b/p99/p19.neb
new file mode 100644
index 0000000..09ff324
--- /dev/null
+++ b/p99/p19.neb
@@ -0,0 +1,15 @@
+; P19 Rotate a list N places to the left.
+
+(def a (list "a" "b" "c" "d" "e" "f" "g" "h"))
+
+(func rotate (lst cnt)
+    (branch
+        ((eq? 0 cnt) lst)
+        ((> cnt 0)
+            (rotate (append (rest lst) (first lst)) (- cnt 1)))
+        ((< cnt 0)
+            (rotate (prepend (most lst) (last lst)) (+ cnt 1)))))
+
+(print (->string a))
+(print (->string (rotate a 3)))
+(print (->string (rotate a (- 2))))
diff --git a/p99/p20.neb b/p99/p20.neb
new file mode 100644
index 0000000..06b5e60
--- /dev/null
+++ b/p99/p20.neb
@@ -0,0 +1,21 @@
+; P20 Remove the K'th element from a list.
+
+(def a (list "a" "b" "c" "d"))
+
+(func enumerate (lst)
+    (def ret (list))
+    (for-each lst
+        (redef ret (append ret (list (+ 1 (length ret)) _item_))))
+    ret)
+
+(func extend (lst1 lst2)
+    (reduce append lst2 lst1))
+
+; using slices
+(func remove-at-slice (lst idx)
+    (extend
+        (slice lst 1 (- idx 1))
+        (slice lst (+ idx 1))))
+
+(print (->string a))
+(print (->string (remove-at-slice a 2)))
diff --git a/p99/p21.neb b/p99/p21.neb
new file mode 100644
index 0000000..8b465e9
--- /dev/null
+++ b/p99/p21.neb
@@ -0,0 +1,16 @@
+; P21 Insert an element at a given position into a list
+
+(def a (list "a" "b" "c" "d"))
+
+(func extend (lst1 lst2)
+    (reduce append lst2 lst1))
+
+(func insert-at (item lst idx)
+    (extend
+        (slice lst 1 (- idx 1))
+        (prepend (slice lst idx) item)))
+            ;(slice lst idx)
+            ;(append (slice lst 1 (- idx 1)) item)))
+
+(print (->string a))
+(print (->string (insert-at "f" a 2)))