# MIT License, Copyright (c) 2022 Marvin Borner
# Lists in Church/Boehm-Berarducci encoding using pairs
# implementations are generally lazy (except when they're broken)
# TODO: Replace fold/map/etc. with faster LC native logic

:import std/Combinator .
:import std/Pair P
:import std/Logic .
:import std/Number/Ternary .

# empty list element
empty false ⧗ (List a)

# returns true if a list is empty
empty? [0 [[[false]]] true] ⧗ (List a) → Boolean

∅?‣ empty?

:test (∅?empty) (true)

# creates list with single element
singleton [P.pair 0 empty] ⧗ a → (List a)

{}‣ singleton

# prepends an element to a list
cons P.pair ⧗ a → (List a) → (List a)

…:… cons

:test ((+1) : {}(+2)) (P.pair (+1) (P.pair (+2) empty))
:test (∅?({}(+2))) (false)

# returns the head of a list or empty
head P.fst ⧗ (List a) → a

^‣ head

:test (^((+1) : {}(+2))) ((+1))

# returns the tail of a list or empty
tail P.snd ⧗ (List a) → (List a)

~‣ tail

:test (~((+1) : {}(+2))) ({}(+2))

# returns the length of a list in balanced ternary
length z [[[rec]]] (+0) ⧗ (List a) → Number
	rec ∅?0 case-end case-inc
		case-inc 2 ++1 ~0
		case-end 1

∀‣ length

:test (∀((+1) : {}(+2))) ((+2))
:test (∀empty) ((+0))

# returns the element at index in list
index z [[[rec]]] ⧗ (List a) → Number → a
	rec ∅?0 case-end case-index
		case-index =?1 ^0 (2 --1 ~0)
		case-end empty

…!!… \index

:test (((+1) : ((+2) : {}(+3))) !! (+0)) ((+1))
:test (((+1) : ((+2) : {}(+3))) !! (+2)) ((+3))
:test (((+1) : ((+2) : {}(+3))) !! (-1)) (empty)
:test (((+1) : ((+2) : {}(+3))) !! (+3)) (empty)

# constructs a list of successively reduced values
scanl z [[[[1 : rec]]]] ⧗ (b → a → b) → b → (List a) → (List b)
	rec ∅?0 case-end case-scan
		case-scan 3 2 (2 1 ^0) ~0
		case-end 0

:test (scanl …+… (+0) ((+1) : ((+2) : {}(+3)))) ((+0) : ((+1) : ((+3) : {}(+6))))

# applies a left fold on a list
foldl z [[[[rec]]]] ⧗ (b → a → b) → b → (List a) → b
	rec ∅?0 case-end case-fold
		case-fold 3 2 (2 1 ^0) ~0
		case-end 1

:test ((foldl …+… (+0) ((+1) : ((+2) : {}(+3)))) =? (+6)) (true)
:test ((foldl …-… (+6) ((+1) : ((+2) : {}(+3)))) =? (+0)) (true)

# foldl without starting value
foldl1 [[foldl 1 ^0 ~0]] ⧗ (a → a → a) → (List a) → a

# applies a right fold on a list
foldr [[[z [[rec]] 0]]] ⧗ (a → b → b) → b → (List b) → b
	rec ∅?0 case-end case-fold
		case-fold 4 ^0 (1 ~0)
		case-end 3

:test ((foldr …+… (+0) ((+1) : ((+2) : {}(+3)))) =? (+6)) (true)
:test ((foldr …-… (+2) ((+1) : ((+2) : {}(+3)))) =? (+0)) (true)

# foldr without starting value
foldr1 [[foldl 1 ^0 ~0]] ⧗ (a → a → a) → (List a) → a

# applies or to all list elements
lor? foldr or? false ⧗ (List Boolean) → Boolean

⋁?‣ lor?

:test (⋁?(true : {}true)) (true)
:test (⋁?(true : {}false)) (true)
:test (⋁?(false : {}false)) (false)

# applies and to all list elements
land? foldr and? true ⧗ (List Boolean) → Boolean

⋀?‣ land?

:test (⋀?(true : {}true)) (true)
:test (⋀?(true : {}false)) (false)
:test (⋀?(false : {}false)) (false)

# reverses a list
reverse foldl \cons empty ⧗ (List a) → (List a)

<~>‣ reverse

:test (<~>((+1) : ((+2) : {}(+3)))) ((+3) : ((+2) : {}(+1)))

# creates list out of n terms
# TODO: use balanced ternary
# TODO: fix/remove incorrect type?
list [0 [[[2 (0 : 1)]]] reverse empty] ⧗ (List a) → Unary → b → (List b)

# appends two lists
append z [[[rec]]] ⧗ (List a) → (List a) → (List a)
	rec ∅?1 case-end case-append
		case-append ^1 : (2 ~1 0)
		case-end 0

…++… append

:test ({}(+1) ++ empty) ({}(+1))
:test (empty ++ {}(+1)) ({}(+1))
:test (empty ++ empty) (empty)
:test (((+1) : ((+2) : {}(+3))) ++ {}(+4)) ((+1) : ((+2) : ((+3) : {}(+4))))

# appends an element to a list
snoc [[1 ++ {}0]] ⧗ (List a) → a → (List a)

…;… snoc

:test (empty ; (+1)) ({}(+1))
:test ({}(+1) ; (+2)) ((+1) : {}(+2))

# maps each element to a function
map z [[[rec]]] ⧗ (a → b) → (List a) → (List b)
	rec ∅?0 case-end case-map
		case-map (1 ^0) : (2 1 ~0)
		case-end empty

…<$>… map

:test (++‣ <$> ((+1) : ((+2) : {}(+3)))) ((+2) : ((+3) : {}(+4)))

# filters a list based on a predicate
filter z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a)
	rec ∅?0 case-end case-filter
		case-filter 1 ^0 (cons ^0) i (2 1 ~0)
		case-end empty

…<#>… \filter

:test (((+1) : ((+0) : {}(+3))) <#> zero?) ({}(+0))

# returns the last element of a list
# - slow algorithm:
#   last z [[rec]]
#   	rec ∅?0 case-end case-last
#   		case-last ∅?(~0) ^0 (1 ~0)
#   		case-end empty
# - taking the first element of the reversed list is actually way faster because laziness
last ^‣ ∘ <~>‣ ⧗ (List a) → a

_‣ last

:test (_((+1) : ((+2) : {}(+3)))) ((+3))

# returns everything but the last element of a list
init z [[rec]] ⧗ (List a) → (List a)
	rec ∅?0 case-end case-init
		case-init ∅?(~0) empty (^0 : (1 ~0))
		case-end empty

:test (init ((+1) : ((+2) : {}(+3)))) ((+1) : {}(+2))

# concatenates a list of lists to one list
concat foldr append empty ⧗ (List a) → (List a) → (List a)

:test (concat (((+1) : {}(+2)) : {}((+3) : {}(+4)))) ((+1) : ((+2) : ((+3) : {}(+4))))
:test (concat ("a" : {}"b")) ("ab")

# maps a function returning list of list and concatenates
concat-map concat ∘∘ map ⧗ (a → (List b)) → (List a) → (List b)

:test (concat-map [-0 : {}0] ((+1) : {}(+2))) ((-1) : ((+1) : ((-2) : {}(+2))))

# zips two lists discarding excess elements
zip z [[[rec]]] ⧗ (List a) → (List b) → (List (Pair a b))
	rec (∅?1 ⋁? ∅?0) case-end case-zip
		case-zip (^1 : ^0) : (2 ~1 ~0)
		case-end empty

:test (zip ((+1) : {}(+2)) ((+2) : {}(+1))) (((+1) : (+2)) : {}((+2) : (+1)))

# zips three lists discarding excess elements
# TODO: add/use triple type (list element types can be different)
zip3 z [[[[rec]]]] ⧗ (List a) → (List a) → (List a) → (List (List a))
	rec (∅?2 ⋁? ∅?1 ⋁? ∅?0) case-end case-zip
		case-zip (^2 : (^1 : {}(^0))) : (3 ~2 ~1 ~0)
		case-end empty

:test (zip3 ((+1) : {}(+2)) ((+2) : {}(+1)) ((+3) : {}(+0))) (((+1) : ((+2) : {}(+3))) : {}((+2) : ((+1) : {}(+0))))

# applies pairs of the zipped list as arguments to a function
zip-with z [[[[rec]]]] ⧗ (a → b → c) → (List a) → (List b) → (List c)
	rec ∅?1 case-end case-zip
		case-zip ∅?0 empty ((2 ^1 ^0) : (3 2 ~1 ~0))
		case-end empty

:test (zip-with …+… ((+1) : {}(+2)) ((+2) : {}(+1))) ((+3) : {}(+3))

# list comprehension
{…|…} map ⧗ (a → b) → (List a) → (List b)

:test ({ ++‣ | ((+0) : {}(+2)) }) ((+1) : {}(+3))

# doubled list comprehension
{…|…,…} zip-with ⧗ (a → b → c) → (List a) → (List b) → (List c)

:test ({ …+… | ((+0) : {}(+2)) , ((+1) : {}(+3)) }) ((+1) : {}(+5))

# returns first n elements of a list
take z [[[rec]]] ⧗ Number → (List a) → (List a)
	rec ∅?0 case-end case-take
		case-take =?1 empty (^0 : (2 --1 ~0))
		case-end empty

:test (take (+2) ((+1) : ((+2) : {}(+3)))) ((+1) : {}(+2))

# takes elements while a predicate is satisfied
take-while z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a)
	rec ∅?0 case-end case-take
		case-take 1 ^0 (^0 : (2 1 ~0)) empty
		case-end empty

:test (take-while zero? ((+0) : ((+0) : {}(+1)))) ((+0) : {}(+0))

# removes first n elements of a list
drop z [[[rec]]] ⧗ Number → (List a) → (List a)
	rec ∅?0 case-end case-drop
		case-drop =?1 0 (2 --1 ~0)
		case-end empty

:test (drop (+2) ((+1) : ((+2) : {}(+3)))) ({}(+3))

# removes elements from list while a predicate is satisfied
drop-while z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List a)
	rec ∅?0 case-end case-drop
		case-drop 1 ^0 (2 1 ~0) 0
		case-end empty

:test (drop-while zero? ((+0) : ((+0) : {}(+1)))) ({}(+1))

# returns all combinations of two lists
cross [[concat-map [map [1 : 0] 1] 1]] ⧗ (List a) → (List b) → (List (Pair a b))

:test (cross "ab" "cd") (('a' : 'c') : (('a' : 'd') : (('b' : 'c') : {}('b' : 'd'))))

# returns all combinations of three lists
# TODO: add/use triple type (list element types can be different)
cross3 [[[concat-map [concat-map [map [2 : (1 : {}0)] 2] 2] 2]]] ⧗ (List a) → (List a) → (List a) → (List (List a))

# :test (cross "ab" "cd") (('a' : 'c') : (('a' : 'd') : (('b' : 'c') : {}('b' : 'd'))))

# returns pair of take-while and drop-while
span [[(take-while 1 0) : (drop-while 1 0)]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a))

:test (span (\les? (+3)) ((+1) : ((+2) : ((+4) : {}(+1))))) (((+1) : {}(+2)) : ((+4) : {}(+1)))

# same as span but with inverted predicate
# slower but equivalent: span ∘ (…∘… ¬‣)
break [[left : right]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a))
	left take-while (¬‣ ∘ 1) 0
	right drop-while (¬‣ ∘ 1) 0

:test (break (\gre? (+3)) ((+1) : ((+2) : ((+4) : {}(+1))))) (((+1) : {}(+2)) : ((+4) : {}(+1)))

# groups list by eq predicate
group-by z [[[rec]]] ⧗ (a → a → Boolean) → (List a) → (List (List a))
	rec ∅?0 case-end case-group
		case-group build (span (1 ^0) ~0)
			build [(^1 : ^0) : (3 2 ~0)]
		case-end empty

:test (group-by [[(0 - 1) <? (+2)]] ((+1) : ((+2) : ((+3) : {}(+4))))) (((+1) : {}(+2)) : {}((+3) : {}(+4)))

# splits a list into a pair of two lists based on predicate, drops match
split-by [[left : right]] ⧗ (a → Boolean) → (List a) → (Pair (List a) (List a))
	left take-while (¬‣ ∘ 1) 0
	right fix (drop-while (¬‣ ∘ 1) 0)
		fix [∅?0 empty ~0]

:test (split-by (…=?… (+1)) ((+2) : ((+1) : ((+3) : {}(+2))))) ({}(+2) : ((+3) : {}(+2)))

# splits a list into lists based on predicate, drops match
split-list-by z [[[rec]]] ⧗ (a → Boolean) → (List a) → (List (List a))
	rec ∅?0 case-end case-split
		case-split build (split-by 1 0)
			build [^0 : (3 2 ~0)]
		case-end empty

:test (split-list-by (…=?… (+1)) ((+2) : ((+1) : ((+3) : {}(+2))))) ({}(+2) : {}((+3) : {}(+2)))

# sorts a list of numbers in ascending order using non-inplace (obviously) quicksort
sort-asc z [[rec]]
	rec ∅?0 case-end case-sort
		case-sort (1 lesser) ++ {}(^0) ++ (1 greater)
			lesser ~0 <#> (\les? ^0)
			greater ~0 <#> (\geq? ^0)
		case-end empty

:test (sort-asc ((+3) : ((+2) : {}(+1)))) ((+1) : ((+2) : {}(+3)))

# sorts a list of numbers in descending order using non-inplace (obviously) quicksort
sort-desc z [[rec]]
	rec ∅?0 case-end case-sort
		case-sort (1 greater) ++ {}(^0) ++ (1 lesser)
			greater ~0 <#> (\geq? ^0)
			lesser ~0 <#> (\les? ^0)
		case-end empty

:test (sort-desc ((+1) : ((+2) : {}(+3)))) ((+3) : ((+2) : {}(+1)))

# inserts an element into a ascendingly sorted list
insert-sorted [go ∘ (span (\les? 0))]
	go [^0 ++ (1 : ~0)]

:test (insert-sorted (+3) ((+1) : ((+2) : {}(+4)))) ((+1) : ((+2) : ((+3) : {}(+4))))

# returns true if any element in a list matches a predicate
any? ⋁?‣ ∘∘ map ⧗ (a → Boolean) → (List a) → Boolean

:test (any? (\gre? (+2)) ((+1) : ((+2) : {}(+3)))) (true)
:test (any? (\gre? (+2)) ((+1) : ((+2) : {}(+2)))) (false)

# returns true if all elements in a list match a predicate
all? ⋀?‣ ∘∘ map ⧗ (a → Boolean) → (List a) → Boolean

:test (all? (\gre? (+2)) ((+3) : ((+4) : {}(+5)))) (true)
:test (all? (\gre? (+2)) ((+4) : ((+3) : {}(+2)))) (false)

# returns true if element is part of a list based on eq predicate
in? …∘… any? ⧗ (a → a → Boolean) → a → (List a) → Boolean

:test (in? …=?… (+3) ((+1) : ((+2) : {}(+3)))) (true)
:test (in? …=?… (+0) ((+1) : ((+2) : {}(+3)))) (false)

# returns true if all elements of one list are equal to corresponding elements of other list
eq? ⋀?‣ ∘∘∘ zip-with ⧗ (a → a → Boolean) → (List a) → Boolean

:test (eq? …=?… ((+1) : {}(+2)) ((+1) : {}(+2))) (true)
:test (eq? …=?… ((+1) : {}(+2)) ((+2) : {}(+2))) (false)
:test (eq? …=?… empty empty) (true)

# finds the first index that matches a predicate
find-index z [[[rec]]] ⧗ (a → Boolean) → (List a) → Number
	rec ∅?0 case-end case-find
		case-find (1 ^0) (+0) !(2 1 ~0)
			!‣ [<?0 0 ++0]
		case-end (-1)

:test (find-index (…=?… (+2)) ((+1) : ((+2) : ((+3) : {}(+2))))) ((+1))
:test (find-index (…=?… (+4)) ((+1) : ((+2) : ((+3) : {}(+2))))) ((-1))

# removes first element that match an eq predicate
remove z [[[[rec]]]] ⧗ (a → a → Boolean) → a → (List a) → (List a)
	rec ∅?0 case-end case-remove
		case-remove (2 ^0 1) ~0 (^0 : (3 2 1 ~0))
		case-end empty

:test (remove …=?… (+2) ((+1) : ((+2) : ((+3) : {}(+2))))) ((+1) : ((+3) : {}(+2)))

# removes duplicates from list based on eq predicate (keeps first occurrence)
nub z [[[rec]]] ⧗ (a → a → Boolean) → (List a) → (List a)
	rec ∅?0 case-end case-nub
		case-nub ^0 : (2 1 (~0 <#> [¬(2 0 ^1)]))
		case-end empty

:test (nub …=?… ((+1) : ((+2) : {}(+3)))) ((+1) : ((+2) : {}(+3)))
:test (nub …=?… ((+1) : ((+2) : {}(+1)))) ((+1) : {}(+2))

# returns a list with infinite-times an element
repeat z [[rec]] ⧗ a → (List a)
	rec 0 : (1 0)

:test (take (+3) (repeat (+4))) ((+4) : ((+4) : {}(+4)))

# returns a list with n-times an element
replicate \(g take repeat) ⧗ Number → a → (List a)

:test (replicate (+3) (+4)) ((+4) : ((+4) : {}(+4)))

# pads a list at end until its length is n
pad-right [[[0 ++ (replicate |(2 - ∀0) 1)]]] ⧗ Number → a → (List a) → (List a)

:test (pad-right (+6) 'a' "hah") ("hahaaa")

# pads a list at start until its length is n
pad-left [[[(replicate (2 - ∀0) 1) ++ 0]]] ⧗ Number → a → (List a) → (List a)

:test (pad-left (+6) 'a' "hah") ("aaahah")

# returns an infinite list repeating a finite list
cycle z [[rec]] ⧗ (List a) → (List a)
	rec 0 ++ (1 0)

:test (take (+6) (cycle "ab")) ("ababab")

# returns a list with infinite-times previous (or start) value applied to a function
iterate z [[[rec]]] ⧗ (a → a) → a → (List a)
	rec 0 : (2 1 (1 0))

:test (take (+5) (iterate ++‣ (+0))) (((+0) : ((+1) : ((+2) : ((+3) : {}(+4))))))
:test (take (+2) (iterate (%‣ ∘ dec) (+5))) (((+5) : {}(+4)))
:test (take (+5) (iterate i (+4))) (take (+5) (repeat (+4)))
:test (take (+0) (iterate ++‣ (+0))) (empty)