List.ark

(import std.Math)

# @brief Reverse a given list and return a new one
# @details The original list is not modified
# @param list the list to reverse
# =begin
# (list:reverse [1 2 3])  # [3 2 1]
# =end
# @author https://github.com/SuperFola
(let reverse (fun (_L) (builtin__list:reverse _L)))

# @brief Search an element in a List
# @details The original list is not modified. Return -1 when not found
# @param list the List to search in
# @param value the element to search
# =begin
# (list:find [1 2 3] 1)  # 0
# (list:find [1 2 3] 0)  # -1
# =end
# @author https://github.com/SuperFola
(let find (fun (_L _x) (builtin__list:find _L _x)))

# @brief Search an element in a List
# @details The original List is not modified. Return -1 when not found
# @param list the List to search in
# @param x the element to search for
# @param startIndex index to start searching from
# =begin
# (list:findAfter [1 2 3] 1 0)  # 0
# (list:findAfter [1 2 3] 1 1)  # -1
# =end
# @author https://github.com/SuperFola
(let findAfter (fun (_L _x _idx) (builtin__list:find _L _x _idx)))

# @brief Search an element in a List with a predicate
# @details The original List is not modified. Return nil when not found
# @param list the List to search in
# @param pred unary Function returning a boolean
# =begin
# (list:findIf [1 2 3] math:even?)  # 1
# (list:findIf [1 3 5] math:even?)  # nil
# =end
# @author https://github.com/SuperFola
(let findIf (fun (_L _f) {
  (mut _i 0)
  (mut _output nil)
  (while (< _i (len _L)) {
    (if (_f (@ _L _i))
      {
        (set _output _i)
        (set _i (len _L)) })
    (set _i (+ 1 _i)) })
  _output }))

# @brief Search for a set of contiguous elements inside a list
# @details The original List is not modified. Return nil when not found
# @param list the List to search in
# @param sub the elements to search for
# =begin
# (list:search [1 2 3 4 5 6] [2 3 4])  # 1
# (list:search [1 2 3 4 5 6] [2 4])  # nil
# =end
# @author https://github.com/SuperFola
(let search (fun ((ref _L) (ref _s)) {
  (assert (not (empty? _s)) "The sublist to look for can't be empty")
  (mut _i (find _L (head _s)))
  (if (!= -1 _i)
    {
      (mut _continue true)
      (mut _output nil)

      (while _continue {
        (mut _ii _i)
        (mut _j 0)
        (mut _ok true)
        (while (and _ok (< _j (len _s)) (< _ii (len _L)))
          (if (!= (@ _L _ii) (@ _s _j))
            (set _ok false)
            {
              (set _j (+ 1 _j))
              (set _ii (+ 1 _ii)) }))
        (if (and _ok (= _j (len _s)))
          {
            (set _continue false)
            (set _output _i) })
        (if (>= _i (len _L))
          (set _continue false))
        (set _i (+ 1 _i)) })
      _output }
    nil) }))

# @brief Search for the first element in the list which is not ordered before value and return its index
# @details The original List is not modified. Expect the List to be sorted. Return nil when not found
# @param list the List to search in
# @param x element to search for
# =begin
# (let prices [100.0 101.5 102.5 102.5 107.3])
# (list:lowerBound prices 102.5)  # 2
# (list:lowerBound prices 110)  # nil
# =end
# @author https://github.com/SuperFola
(let lowerBound (fun ((ref _L) _x) {
  (mut _it nil)
  (mut _count (len _L))
  (mut _first 0)

  (while (> _count 0) {
    (let _step (math:floordiv _count 2))
    (set _it (+ _first _step))
    (if (and (< _it (len _L)) (< (@ _L _it) _x))
      {
        (set _it (+ 1 _it))
        (set _first _it)
        (set _count (+ (- _count _step) 1)) }
      (set _count _step)) })

  (if (< _first (len _L))
    _first
    nil) }))

# @brief Search for the first element in the list which is ordered after value and return its index
# @details The original List is not modified. Expect the List to be sorted. Return nil when not found
# @param list the List to search in
# @param x element to search for
# =begin
# (let prices [100.0 101.5 102.5 102.5 107.3])
# (list:upperBound prices 102.5)  # 4
# (list:upperBound prices 110)  # nil
# =end
# @author https://github.com/SuperFola
(let upperBound (fun ((ref _L) _x) {
  (mut _it nil)
  (mut _count (len _L))
  (mut _first 0)

  (while (> _count 0) {
    (let _step (math:floordiv _count 2))
    (set _it (+ _first _step))
    (if (and (< _it (len _L)) (>= _x (@ _L _it)))
      {
        (set _it (+ 1 _it))
        (set _first _it)
        (set _count (+ (- _count _step) 1)) }
      (set _count _step)) })

  (if (< _first (len _L))
    _first
    nil) }))

# @brief Check if an element is in a sorted List
# @details The original List is not modified. Expect the List to be sorted
# @param list the List to search in
# @param x element to search for
# =begin
# (let prices [1 3 5 9])
# (list:binarySearch prices 1)  # true
# (list:binarySearch prices 2)  # false
# =end
# @author https://github.com/SuperFola
(let binarySearch (fun ((ref _L) _x) {
  (let _first (lowerBound _L _x))
  (and (< _first (len _L)) (>= _x (@ _L _first))) }))

# @brief Search if an element is in a List
# @details The original list is not modified
# @param list the List to search in
# @param value the element to search
# =begin
# (list:contains? [1 2 3] 1)  # true
# (list:contains? [1 2 3] 0)  # false
# =end
# @author https://github.com/SuperFola
(let contains? (fun (_L _x) (!= -1 (find _L _x))))

# @brief Get a slice from a List
# @details The original list is not modified
# @param list the list to slice
# @param start included, must be positive
# @param end not included, must be positive and smaller than the list
# @param step must be greater than 0
# =begin
# (list:slice [1 2 3 4 5] 1 4 2)  # [2 4]
# =end
# @author https://github.com/SuperFola
(let slice (fun (_L _start _end _step) (builtin__slice _L _start _end _step)))

# @brief Get a slice from a List with a step of 1
# @details The original list is not modified
# @param list the list to slice
# @param start included, must be positive
# @param end not included, must be positive and smaller than the list
# =begin
# (list:slice1 [1 2 3 4 5] 1 3)  # [2 3 4]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let slice1 (fun (_L _start _end) (builtin__slice _L _start _end 1)))

# @brief Sort a List and return a new one
# @details The original list is not modified
# @param list the list to sort
# =begin
# (list:sort [4 2 3])  # [1 2 4]
# =end
# @author https://github.com/SuperFola
(let sort (fun (_L) (builtin__list:sort _L)))

# @brief Check if a List is sorted
# @details The original list is not modified
# @param list List to check
# =begin
# (list:sorted? [4 2 3])  # false
# (list:sorted? [])  # true
# (list:sorted? [1])  # true
# (list:sorted? [1 2 5])  # true
# =end
# @author https://github.com/SuperFola
(let sorted? (fun ((ref _L)) {
  (mut _i 0)
  (mut _ok true)

  (while (and _ok (< _i (- (len _L) 1))) {
    (set _ok (<= (@ _L _i) (@ _L (+ 1 _i))))
    (set _i (+ 1 _i)) })

  (if (<= (len _L) 1)
    true
    _ok) }))

# @brief Generate a List of n copies of an element
# @param count the number of copies
# @param value the element to copy
# =begin
# (list:fill 4 nil)  # [nil nil nil nil]
# =end
# @author https://github.com/SuperFola
(let fill (fun (_count _val) (builtin__list:fill _count _val)))

# @brief Generate a List of n zeros
# @param count the number of zeros
# =begin
# (list:zeros 4)  # [0 0 0 0]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let zeros (fun (_count) (builtin__list:fill _count 0)))

# @brief Generate a List of n ones
# @param count the number of ones
# =begin
# (list:ones 4)  # [1 1 1 1]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let ones (fun (_count) (builtin__list:fill _count 1)))

# @brief Modify a given list and return a new one
# @details The original list is not modified
# @param list the list to modify
# @param index the index of the element to modify
# @param value the new element
# =begin
# (list:setAt [1 2 3] 0 5)  # [5 2 3]
# =end
# @author https://github.com/SuperFola
(let setAt (fun (_L _index _x) (builtin__list:setAt _L _index _x)))

(let _stopIteration_helper (fun () (assert false "This shouldn't be called")))

# @brief Value to return from functions passed to forEach, enumerate, window... to stop iteration early
# @author https://github.com/SuperFola
(let stopIteration _stopIteration_helper)

# @brief Iterate over a given list and run a given function on every element.
# @param _data the list to iterate over
# @param _func the function to call on each element. It can return list:stopIteration to stop iteration early
# @details The original list is not modified. Returns true if it returns early, false otherwise
# =begin
# (let collection [1 2 5 12])
# (list:forEach collection (fun (element) {
#     (print element) }))
# =end
# @author https://github.com/SuperFola
(let forEach (fun ((ref _data) _func) {
  (mut _index 0)
  (mut _early false)

  (while (< _index (len _data)) {
    (mut _element (@ _data _index))
    (if (= (_func _element) stopIteration)
      {
        (set _index (len _data))
        (set _early true) })
    (set _index (+ 1 _index)) })

  _early }))

# @brief Iterate over a given list and run a given function on every element, passing its index as well.
# @param _L the list to iterate over
# @param _func a binary function to call on each element with (index, element). It can return list:stopIteration to stop iteration early
# @details The original list is not modified. Returns true if it returns early, false otherwise
# =begin
# (let collection [1 2 5 12])
# (list:enumerate collection (fun (idx element) {
#     (print idx " " element) }))
# =end
# @author https://github.com/SuperFola
(let enumerate (fun ((ref _L) _func) {
  (mut _index 0)
  (mut _early false)

  (while (< _index (len _L)) {
    (mut _element (@ _L _index))
    (if (= (_func _index _element) stopIteration)
      {
        (set _index (len _L))
        (set _early true) })

    (set _index (+ 1 _index)) })

  _early }))

# @brief Iterate over a given list and multiply all the elements with the others.
# @param _L the list to iterate over
# @details The original list is not modified.
# =begin
# (let collection [1 2 5 12])
# (let p (list:product collection))  # => 120
# =end
# @author https://github.com/Unactived
(let product (fun ((ref _L)) {
  (mut _index 0)
  (mut _output 1)

  (while (< _index (len _L)) {
    (set _output (* _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Cumulative product of a list
# @param _L the list to iterate over
# @details The original list is not modified.
# =begin
# (let collection [1 2 3 4])
# (let p (list:cumulativeProduct collection))  # => [1 2 6 24]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let cumulativeProduct (fun ((ref _L)) {
  (mut _index 0)
  (mut _output [])
  (mut _prev 1)

  (while (< _index (len _L)) {
    (append! _output (* _prev (@ _L _index)))
    (set _prev (@ _output -1))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Iterate over a given list and sum all the elements.
# @param _L the list to iterate over
# @details The original list is not modified.
# =begin
# (let collection [1 2 5 12])
# (let p (list:sum collection))  # => 20
# =end
# @author https://github.com/Unactived
(let sum (fun ((ref _L)) {
  (mut _index 0)
  (mut _output 0)

  (while (< _index (len _L)) {
    (set _output (+ _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Cumulative sum of a list
# @param _L the list to iterate over
# @details The original list is not modified.
# =begin
# (let collection [1 2 5 12])
# (let p (list:cumulativeSum collection))  # => [1 3 8 20]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let cumulativeSum (fun ((ref _L)) {
  (mut _index 0)
  (mut _output [])
  (mut _prev 0)

  (while (< _index (len _L)) {
    (append! _output (+ _prev (@ _L _index)))
    (set _prev (@ _output -1))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Find the minimum in a list of numbers
# @param _L list of numbers
# @details The original list is not modified.
# =begin
# (let value (list:min [0 1 2 3 5 8]))  # 0
# =end
# @author https://github.com/SuperFola
(let min (fun ((ref _L)) {
  (mut _index 0)
  (mut _output nil)

  (while (< _index (len _L)) {
    (if (or (nil? _output) (< (@ _L _index) _output))
      (set _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Find the maximum in a list of numbers
# @param _L list of numbers
# @details The original list is not modified.
# =begin
# (let value (list:max [0 1 2 3 5 8]))  # 8
# =end
# @author https://github.com/SuperFola
(let max (fun ((ref _L)) {
  (mut _index 0)
  (mut _output nil)

  (while (< _index (len _L)) {
    (if (or (nil? _output) (> (@ _L _index) _output))
      (set _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Find the minimum and the maximum in a list of numbers
# @param _L list of numbers
# @details The original list is not modified.
# =begin
# (let value (list:minMax [0 1 2 3 5 8]))  # [0 8]
# =end
# @author https://github.com/SuperFola
(let minMax (fun ((ref _L)) {
  (mut _index 0)
  (mut _min nil)
  (mut _max nil)

  (while (< _index (len _L)) {
    (let _val (@ _L _index))

    (if (or (nil? _min) (< _val _min))
      (set _min _val))
    (if (or (nil? _max) (> _val _max))
      (set _max _val))

    (set _index (+ 1 _index)) })
  [_min _max] }))

# @brief Find the median in a list of numbers
# @param _L list of numbers
# @details The original list is not modified.
# =begin
# (let value (list:median [0 1 2 3 5 8]))  # 2.5
# =end
# @author https://github.com/SuperFola
(let median (fun ((ref _L)) {
  (let _n (len _L))
  (if (= 0 _n)
    nil
    {
      (let _s (sort _L))
      (if (math:even? _n)
        (/ (+ (@ _s (- (/ _n 2) 1)) (@ _s (/ _n 2))) 2)
        (@ _s (/ _n 2))) }) }))

# @brief Keep elements in a given list if they follow a predicate
# @param _L the list to work on
# @param _f the predicate
# @details The original list is not modified.
# =begin
# (import std.Math)
# (print (list:filter [1 2 3 4 5 6 7 8 9] math:even?))  # [2 4 6 8]
# =end
# @author https://github.com/rstefanic
(let filter (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L)) {
    (if (_f (@ _L _index)) (append! _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Apply a given function to each element of a list. If nil is returned, the element is discarded
# @param _L the list to work on
# @param _f the function to apply to each element
# @details The original list is not modified.
# =begin
# (let nums [1 2 3 4 5 6 7 8 9])
# (print
#   (list:collect
#     nums
#     (fun (e)
#       (if (= 0 (mod e 2)) (* 10 e)))))
# # [20 40 60 80]
# =end
# @author https://github.com/SuperFola
(let collect (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L)) {
    (let _result (_f (@ _L _index)))
    (if (not (nil? _result)) (append! _output _result))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Sort elements in a list using a function to compute the key
# @details Use the quicksort algorithm, the original list is not modified.
# @param _L list to sort
# @param _key function called on each element of the list, returning a unique key to use for sorting
# =begin
# (let ranges [[3 5] [10 14] [16 20] [12 18]])
# (let sorted (sortByKey ranges (fun (e) (head e))))
# (print sorted)  # [[3 5] [10 14] [12 18] [16 20]]
# =end
# @author https://github.com/SuperFola
(let sortByKey (fun ((ref _L) _key) {
  (if (empty? _L)
    []
    {
      (let _pivot_val (head _L))
      (let _pivot (_key _pivot_val))

      (mut _rest (tail _L))
      (mut _less (sortByKey (filter _rest (fun (e) (< (_key e) _pivot))) _key))
      (let _more (sortByKey (filter _rest (fun (e) (>= (_key e) _pivot))) _key))

      (concat! _less [_pivot_val] _more)
      _less }) }))

# @brief Apply a given function to each element of a list
# @param _L the list to work on
# @param _f the function to apply to each element
# @details The original list is not modified.
# =begin
# (print (list:map [1 2 3 4 5 6 7 8 9] (fun (e) (* e e))))  # [1 4 9 25 36 49 64 81]
# =end
# @author https://github.com/rstefanic
(let map (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L)) {
    (append! _output (_f (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Fold a given list, starting from the left side
# @param _L the list to work on
# @param _init an init value
# @param _f a function to apply to the list
# @details The original list is not modified.
# =begin
# (let a [1 2 3 4])
# (print (list:foldLeft a 0 (fun (a b) (+ a b))))  # 10
# =end
# @author https://github.com/SuperFola
(let foldLeft (fun ((ref _L) _init _f) {
  (mut _index 0)
  (mut _val _init)

  (while (< _index (len _L)) {
    (set _val (_f _val (@ _L _index)))
    (set _index (+ 1 _index)) })
  _val }))

# @brief Apply a function to the elements of a list to reduce it
# @param _L the list to work on
# @param _f the function to apply
# @details The original list is not modified.
# =begin
# (let cool [1 2 3 4 5 6 7 8 9])
# (print (list:reduce cool (fun (a b) (+ a b))))  # 45
# =end
# @author https://github.com/Unactived
(let reduce (fun ((ref _L) _f) {
  (mut _index 1)
  (mut _output (@ _L 0))

  (while (< _index (len _L)) {
    (set _output (_f _output (@ _L _index)))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Flatten a list
# @param _L the list to work on
# @details The original list is not modified.
# =begin
# (let cool [[1 2 3] [4] 5 6 [7 8] 9])
# (print (list:flatten cool))  # [1 2 3 4 5 6 7 8 9]
# =end
# @author https://github.com/SuperFola
(let flatten (fun ((ref _L)) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L)) {
    (mut _sub (@ _L _index))

    (if (= "List" (type _sub))
      (concat! _output _sub)
      (append! _output _sub))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Apply a given function to each element of a list and then flatten it
# @param _L the list to work on
# @param _f the function to apply to each element
# @details The original list is not modified.
# =begin
# (let cool [1 2 3 4])
# (print (list:flatMap cool (fun (a) [a a])))  # [1 1 2 2 3 3 4 4]
# =end
# @author https://github.com/SuperFola
(let flatMap (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L)) {
    (let _res (_f (@ _L _index)))

    (if (= "List" (type _res))
      (concat! _output _res)
      (append! _output _res))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Get the first n elements of a list
# @details This is equivalent to `list:take`
# @param _L the list to work on
# @param _n the number of elements to take
# @details The original list is not modified.
# =begin
# (print (list:first [1 2 3 4 5 6 7 8 9] 4))  # [1 2 3 4]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let first (fun ((ref _L) _n)
  (if (<= (len _L) _n)
    _L
    (builtin__slice _L 0 _n))))

# @brief Get the last n elements of a list
# @param _L the list to work on
# @param _n the number of elements to take
# @details The original list is not modified.
# =begin
# (print (list:last [1 2 3 4 5 6 7 8 9] 4))  # [6 7 8 9]
# =end
# @author https://github.com/SuperFola
# @require 4.6.0 Requires ArkScript 4.6.0 or later
(let last (fun ((ref _L) _n)
  (if (<= (len _L) _n)
    _L
    (builtin__slice _L (* -1 _n) nil))))

# @brief Take the first n elements of
# @param _L the list to work on
# @param _n the number of elements to take
# @details The original list is not modified.
# =begin
# (print (list:take [1 2 3 4 5 6 7 8 9] 4))  # [1 2 3 4]
# =end
# @author https://github.com/rstefanic
(let take (fun ((ref _L) (mut _n)) {
  (mut _index 0)
  (mut _output [])
  (set _n (math:min _n (len _L)))

  (while (< _index _n) {
    (append! _output (@ _L _index))
    (set _index (+ 1 _index)) })
  _output }))

# @brief Take the first n elements of a list, given a predicate
# @param _L the list to work on
# @param _f the predicate
# @details The original list is not modified.
# =begin
# (print (list:takeWhile [1 2 3 4 5 6 7 8 9 10] (fun (a) (< a 4))))  # [1 2 3]
# =end
# @author https://github.com/rakista112
(let takeWhile (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])
  (mut _continue true)

  (while (and (< _index (len _L)) _continue)
    (if (_f (@ _L _index))
      {
        (append! _output (@ _L _index))
        (set _index (+ 1 _index)) }
      (set _continue false)))
  _output }))

# @brief Drop the first n elements of a list
# @param _L the list to work on
# @param _n the number of elements to drop
# @details The original list is not modified.
# =begin
# (let cool-stuff [1 2 3 4 5 6 7 8 9])
# (print (list:drop cool-stuff 4))  # [5 6 7 8 9]
# =end
# @author https://github.com/rstefanic, https://github.com/SuperFola
(let drop (fun ((ref _L) _n)
  (if (< _n (/ (len _L) 2))
    (if (> _n 0)
      (drop (tail _L) (- _n 1))
      _L)
    {
      (mut _index (math:max 0 _n))
      (mut _output [])

      (while (< _index (len _L)) {
        (append! _output (@ _L _index))
        (set _index (+ 1 _index)) })
      _output })))

# @brief Drop the first elements of a list, while they match a given predicate
# @param _L the list to work on
# @param _f the predicate
# @details The original list is not modified.
# =begin
# (let cool-stuff [1 2 3 4 5 6 7 8 9])
# (print (list:dropWhile cool-stuff (fun (a) (< a 4))))  # [4 5 6 7 8 9]
# =end
# @author https://github.com/SuperFola
(let dropWhile (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _output [])

  (while (< _index (len _L))
    (if (_f (@ _L _index))
      (set _index (+ 1 _index))
      (while (< _index (len _L)) {
        (append! _output (@ _L _index))
        (set _index (+ 1 _index)) })))
  _output }))

# @brief Shift the elements of a List to the left, putting the overflow at the end
# @param _L the list to work on
# @param _c Number of elements to move (must be positive)
# @details The original list is not modified.
# =begin
# (list:shiftLeft [1 2 3 4 5] 2)  # [3 4 5 1 2]
# =end
# @author https://github.com/SuperFola
(let shiftLeft (fun ((ref _L) (mut _c)) {
  (assert (>= _c 0) "count must be positive")
  (set _c (mod _c (len _L)))

  (if (or (empty? _L) (= 0 _c))
    _L
    {
      (let _to_shift (first _L _c))
      (let _tail (last _L (- (len _L) _c)))
      (concat _tail _to_shift) }) }))

# @brief Shift the elements of a List to the right, putting the overflow at the beginning
# @param _L the list to work on
# @param _c Number of elements to move (must be positive)
# @details The original list is not modified.
# =begin
# (list:shiftRight [1 2 3 4 5] 2)  # [4 5 1 2 3]
# =end
# @author https://github.com/SuperFola
(let shiftRight (fun ((ref _L) (mut _c)) {
  (assert (>= _c 0) "count must be positive")
  (set _c (mod _c (len _L)))

  (if (or (empty? _L) (= 0 _c))
    _L
    {
      (let _to_shift (last _L _c))
      (let _head (first _L (- (len _L) _c)))
      (concat _to_shift _head) }) }))

# @brief Partition a list in two, given a predicate
# @param _L the list to work on
# @param _f the predicate, accepting the value and its index
# @details The original list is not modified.
# =begin
# (let a [1 2 3])
# (print (list:partition a (fun (c i) (= 0 (mod c 2)))))  # [[2] [1 3]]
# =end
# @author https://github.com/SuperFola
(let partition (fun ((ref _L) _f) {
  (mut _index 0)
  (mut _pass [])
  (mut _fail [])

  (while (< _index (len _L)) {
    (let _val (@ _L _index))
    (if (_f _val _index)
      (append! _pass _val)
      (append! _fail _val))
    (set _index (+ 1 _index)) })

  [_pass _fail] }))

# @brief Unzip a list of [[a b] [c d]...] into [[a c ...] [b d ...]]
# @param _L the list to work on
# @details The original list is not modified.
# =begin
# (let zipped [[1 5] [2 6] [3 7] [4 8]])
# (print (list:unzip zipped))  # [[1 2 3 4] [5 6 7 8]]
# =end
# @author https://github.com/Unactived
(let unzip (fun ((ref _L)) {
  (let _m (len _L))
  (mut _list1 [])
  (mut _list2 [])
  (mut _index 0)

  (while (< _index _m) {
    (mut current (@ _L _index))
    (append! _list1 (@ current 0))
    (append! _list2 (@ current 1))
    (set _index (+ 1 _index)) })
  [_list1 _list2] }))

# @brief Transpose a list of lists or list of strings
# @details The original list is not modified. The smallest element size is used as the limit for selecting values
# @param _L list of lists/strings to transpose
# =begin
# (let data [[1 2 3] [4 5 6] [7 8 9])
# (print (list:transpose data))  # [[1 4 7] [2 5 8] [3 6 9]]
# =end
# @author https://github.com/SuperFola
(let transpose (fun (_L) {
  (mut _output [])
  (mut _i 0)
  (let _width (min (map _L len)))
  (let _height (len _L))

  (while (< _i _width) {
    (mut _column [])
    (mut _k 0)
    (while (< _k _height) {
      (append! _column (@@ _L _k _i))
      (set _k (+ _k 1)) })

    (append! _output _column)
    (set _i (+ 1 _i)) })
  _output }))

# @brief Zip two lists into one: [1 2 3 4] and [5 6 7 8] will give [[1 5] [2 6] [3 7] [4 8]]
# @details Lists must have the same size. Otherwise, only the first (min (len _a) (len _b)) elements will be used.
# @param _a the first list to work on
# @param _b the second list to work on
# @details The original lists are not modified.
# =begin
# (let a [1 2 3 4])
# (let b [5 6 7 8])
# (print (list:zip a b))  # [[1 5] [2 6] [3 7] [4 8]]
# =end
# @author https://github.com/Unactived
(let zip (fun ((ref _a) (ref _b)) {
  (let _m (math:min (len _a) (len _b)))
  (mut _c [])
  (mut _index 0)

  (while (< _index _m) {
    (append! _c [(@ _a _index) (@ _b _index)])
    (set _index (+ 1 _index)) })
  _c }))

# @brief Zip two lists into one, using a filler if one list is shorter: [1 2 3] and [5 6 7 8] will return [[1 5] [2 6] [3 7] [0 8]]
# @param _a the first list to work on
# @param _b the second list to work on
# @param _filler value to use if there is not enough items in one of the lists
# @details The original lists are not modified.
# =begin
# (let a [1 2 3])
# (let b [5 6 7 8])
# (print (list:zipLongest a b 0))  # [[1 5] [2 6] [3 7] [0 8]]
# =end
# @author https://github.com/SuperFola
(let zipLongest (fun ((ref _a) (ref _b) _filler) {
  (let _m (math:max (len _a) (len _b)))
  (mut _c [])
  (mut _index 0)

  (while (< _index _m) {
    (append!
      _c
      [
        (if (< _index (len _a))
          (@ _a _index)
          _filler)
        (if (< _index (len _b))
          (@ _b _index)
          _filler)])
    (set _index (+ 1 _index)) })
  _c }))

# @brief Zip a list elements with their index. [5 6 7 8] will give [[0 5] [1 6] [2 7] [3 8]]
# @param _L the list to iterate over
# @details The original list is not modified.
# =begin
# (let a [5 6 7 8])
# (print (list:zipWithIndex a))  # [[0 5] [1 6] [2 7] [3 8]]
# =end
# @author https://github.com/SuperFola
(let zipWithIndex (fun ((ref _L)) {
  (mut _output [])
  (mut _index 0)
  (let _len (len _L))
  (while (< _index _len) {
    (append! _output [_index (@ _L _index)])
    (set _index (+ 1 _index)) })
  _output }))

# @brief Check if a condition is verified for all elements of a list
# @param _L the list to work on
# @param _f the condition
# =begin
# (let a [1 2 3 4])
# (let f (fun (e) (< e 5)))
# (print (list:forAll a f))  # true
# =end
# @author https://github.com/Gryfenfer97
(let forAll (fun ((ref _L) _f) {
  (mut _verified true)
  (mut _index 0)

  (while (and _verified (< _index (len _L))) {
    (if (not (_f (@ _L _index)))
      (set _verified false))
    (set _index (+ 1 _index)) })
  _verified }))

# @brief Check if a condition if verified for one or more elements of a list
# @param _L the list to work on
# @param _f the condition
# =begin
# (let a [1 2 3 4])
# (let f (fun (e) (< e 3)))
# (print (list:any a f))  # true
# =end
# @author https://github.com/Gryfenfer97
(let any (fun ((ref _L) _f) {
  (mut _verified false)
  (mut _index 0)

  (while (and (not _verified) (< _index (len _L))) {
    (if (_f (@ _L _index))
      (set _verified true))
    (set _index (+ 1 _index)) })
  _verified }))

# @brief Check if a condition can't be verified for any element of a list
# @param _L the list to work on
# @param _f the condition
# =begin
# (let a [1 2 3 4])
# (let f (fun (e) (< e 3)))
# (print (list:none a f))  # false
# (print (list:none [4 5 6] f))  # true
# =end
# @author https://github.com/SuperFola
(let none (fun ((ref _L) _f) (not (any _L _f))))

# @brief Count the number of elements in a list that match a condition
# @param _L the list to work on
# @param _f the condition
# =begin
# (let lst [1 2 3 4 5 6 7 8 9])
# (let is_even (fun (e) (= 0 (mod e 2))))
# (print (list:countIf lst is_even))  # 4
# =end
# @author https://github.com/SuperFola
(let countIf (fun ((ref _L) _f) {
  (mut _i 0)
  (mut _count 0)
  (while (< _i (len _L)) {
    (if (_f (@ _L _i))
      (set _count (+ 1 _count)))
    (set _i (+ 1 _i)) })
  _count }))

# @brief Generate a sequence based on a unary function, initial value and length
# @param _init initial value of the sequence
# @param _f unary function to generate values
# @param _length the sequence length
# =begin
# (let f (fun (x) (+ 7 x)))
# (print (list:iterate 0 f 10))  # [0 7 14 21 28 35 42 49 56 63]
# =end
# @author https://github.com/SuperFola
(let iterate (fun (_init _f _length) {
  (assert (> _length 0) "list:iterate needs a length of at least 1")

  (mut _output [_init])
  (mut _last _init)
  (mut _i 1)
  (while (< _i _length) {
    (set _last (_f _last))
    (append! _output _last)
    (set _i (+ 1 _i)) })
  _output }))

# @brief Generate a sequence of numbers
# @param _init initial value of the sequence
# @param _length the sequence length
# =begin
# (print (list:iota 0 10))  # [0 1 2 3 4 5 6 7 8 9]
# =end
# @author https://github.com/SuperFola
(let iota (fun (_init _length) (iterate _init (fun (_x) (+ 1 _x)) _length)))

# @brief Generate a sequence of numbers
# @param _start initial value of the sequence
# @param _end end value (not included)
# @param _step step to go from one number to the next (0 is not allowed and will generate an error)
# =begin
# (print (list:range 1 5 1))  # [1 2 3 4]
# (print (list:range 10 5 -2))  # [10 8 6]
# =end
# @author https://github.com/SuperFola
(let range (fun (_start _end _step) {
  (assert (!= _step 0) "list:range needs a non-zero step value")

  (mut _output [])
  (mut _last _start)
  (while
    (if (> _step 0)
      (< _last _end)
      (> _last _end))
    {
      (append! _output _last)
      (set _last (+ _last _step)) })

  _output }))

# @brief Chunk a list in sub-lists of size n
# @param _L list to chunk
# @param _length size of the chunks
# =begin
# (let indices (list:iota 1 9))  # [1 2 3 4 5 6 7 8 9]
# (print (list:chunkBy indices 3))  # [[1 2 3] [4 5 6] [7 8 9]]
# =end
# @author https://github.com/SuperFola
(let chunkBy (fun ((ref _L) _length) {
  (assert (> _length 0) "list:chunkBy needs a chunk size of at least 1")
  (mut _output [])
  (mut _current [])
  (let _source_len (len _L))

  (mut _i 0)
  (while (< _i _source_len) {
    (append! _current (@ _L _i))
    (if (= (len _current) _length)
      {
        (append! _output _current)
        (set _current []) })
    (set _i (+ 1 _i)) })

  (if (not (empty? _current)) (append! _output _current))

  _output }))

# @brief Insert an element (or expand a list) at a given position inside a list
# @details The original list is not modified
# @param _L list to insert element(s) in
# @param _index where to insert
# @param _value value to insert
# =begin
# (let a [0])
# (print (list:insert a 1 4))  # [0 4]
# (print (list:insert a 1 [1 2]))  # [0 1 2]
# (let b [0 9])
# (print (list:insert b 1 4))  # [0 4 9]
# (print (list:insert b 1 [1 2]))  # [0 1 2 9]
# =end
# @author https://github.com/SuperFola
(let insert (fun ((ref _L) _index (mut _value)) {
  (let _size (len _L))
  (assert (<= _index _size) "list:insert can not insert a value outside the list")

  (if (!= "List" (type _value))
    (set _value [_value]))

  # insert at beginning
  (if (= 0 _index)
    (concat _value _L)
    # insert at the end
    (if (= _size _index)
      (concat _L _value)
      {
        # insert anywhere
        (let _parts (partition _L (fun (elem i &_index) (< i _index))))
        (concat (head _parts) _value (@ _parts 1)) })) }))

# @brief Create a sliding window of a given size on a list
# @details The original list is not modified. Returns true if it returns early, false otherwise
# @param _L list to iterate over
# @param _size window size, must be at least 1
# @param _f function to call with the window. It can return list:stopIteration to stop iteration early
# =begin
# (let f (fun (lst) (print lst))
# (list:window [1 2 3 4 5] 3 f)
# # [1 2 3]
# # [2 3 4]
# # [3 4 5]
# =end
# @author https://github.com/SuperFola
(let window (fun ((ref _L) _size _f) {
  (assert (> _size 0) "window size must be at least 1")

  (mut _early false)
  (mut _i 0)
  (while (< _i (len _L)) {
    (mut _win [])
    (mut _j 0)
    (while (< _j _size) {
      (append! _win (@ _L (+ _i _j)))
      (set _j (+ 1 _j)) })

    (if (= (_f _win) stopIteration)
      {
        (set _i (len _L))
        (set _early true) })

    (if (>= (+ _i _size) (len _L))
      (set _i (len _L)))
    (set _i (+ 1 _i)) })

  _early }))

# @brief Get the unique values in a given list
# @details The original list is not modified.
# @param _L list to extract unique values from
# =begin
# (let data [1 1 2 3 4 3 4 5])
# (print (list:unique data))  # [1 2 3 4 5]
# =end
# @author https://github.com/SuperFola
(let unique (fun ((ref _L)) {
  (mut _vals (dict))
  (mut _i 0)
  (while (< _i (len _L)) {
    (let v (@ _L _i))
    (if (not (builtin__dict:contains _vals v)) (builtin__dict:add _vals v _i))
    (set _i (+ 1 _i)) })

  (builtin__dict:keys _vals) }))

# @brief Compute the intersection of two lists
# =details-begin
# - The original lists are not modified.
# - The elements appear in the same order they are in _L1.
# - Duplicates are kept: if one list has two `1`, and the other has three, two `1` will be in the output.
# =details-end
# @param _L1 List
# @param _L2 List
# =begin
# (print (list:intersection [1] [2]))  # []
# (print (list:intersection [3 2 1] [1 2 3]))  # [3 2 1]
# (print (list:intersection [1 2 2 1] [2 2]))  # [2 2]
# =end
# @author https://github.com/SuperFola
(let intersection (fun ((ref _L1) (ref _L2)) {
  (mut _target (if (> (len _L2) (len _L1)) _L1 _L2))
  (let _iterate (if (> (len _L2) (len _L1)) _L2 _L1))

  (mut _i 0)
  (mut _output [])
  (while (< _i (len _iterate)) {
    (let _el (@ _iterate _i))
    (let _idx (find _target _el))
    (if (!= -1 _idx)
      {
        (append! _output _el)
        (pop! _target _idx) })
    (set _i (+ _i 1)) })
  _output }))

# @brief Compute the difference of two lists
# =details-begin
# - The original lists are not modified.
# - Elements that are only in one of the two lists are kept.
# - Elements from the longest list are picked first:
# `(print (list:difference [1 2 3] [4 5 6 7]))  # => [4 5 6 7 1 2 3]`
# =details-end
# @param _L1 List
# @param _L2 List
# =begin
# (print (list:difference [1 2 3] [3 2 1]))  # []
# (print (list:difference [1 2 3 4 5] [1 2 3 4 4]))  # [5 4]
# (print (list:difference [1 2] ["a" "b"]))  # [1 2 "a" "b"]
# =end
# @author https://github.com/SuperFola
(let difference (fun ((ref _L1) (ref _L2)) {
  (mut _target (if (> (len _L2) (len _L1)) _L1 _L2))
  (let _iterate (if (> (len _L2) (len _L1)) _L2 _L1))

  (mut _i 0)
  (mut _output [])
  (while (< _i (len _iterate)) {
    (let _el (@ _iterate _i))
    (let _idx (find _target _el))
    (if (= -1 _idx)
      (append! _output _el)
      (pop! _target _idx))
    (set _i (+ _i 1)) })

  (concat _output _target) }))

# @brief Count the occurrences of the elements of a List, and return them a Dict (elem -> count)
# @details The original list is not modified.
# @param _L List
# =begin
# (let data [1 1 2 3 4 3 4 5])
# (print (list:countOccurrences data))  # {1: 2, 2: 1, 3: 2, 4: 2, 5: 1}
# =end
# @author https://github.com/SuperFola
(let countOccurrences (fun ((ref _L)) {
  (mut _items (dict))
  (mut _i 0)
  (while (< _i (len _L)) {
    (let v (@ _L _i))
    (if (not (builtin__dict:contains _items v))
      (builtin__dict:add _items v 1)
      (builtin__dict:add _items v (+ 1 (builtin__dict:get _items v))))
    (set _i (+ 1 _i)) })
  _items }))

# @brief Create a new list from a list of values and indices to get from the first list
# @details The original list is not modified.
# @param _L list to get values from
# @param _indices list of indices of values in _L
# =begin
# (let data [1 1 2 3 4 3 4 5])
# (print (list:select data [0 0 0]))  # [1 1 1]
# (print (list:select data [0 2 3 4]))  # [1 2 3 4]
# =end
# @author https://github.com/SuperFola
(let select (fun ((ref _L) (ref _indices)) {
  (mut _output [])
  (mut _i 0)
  (while (< _i (len _indices)) {
    (let _idx (@ _indices _i))
    (if (< _idx (len _L)) (append! _output (@ _L _idx)))
    (set _i (+ 1 _i)) })
  _output }))

# @brief Compute combinations of length _r from a given list
# @details The original list is not modified.
# @param _L list to get values from
# @param _r number of elements per permutation
# @param _f function to call on each permutation. It can return list:stopIteration to stop iteration early
# =begin
# (let data [0 1 2 3])
# (list:combinations data 3 (fun (perm) (print perm)))
# # [0 1 2]
# # [0 1 3]
# # [0 2 3]
# # [1 2 3]
# =end
# @author https://github.com/SuperFola
(let combinations (fun ((ref _L) _r _f) {
  (let _len (len _L))
  (if (and (<= _r _len) (> _r 0))
    {
      (mut _indices (iota 0 _r))
      (if (!= stopIteration (_f (select _L _indices)))
        {
          (mut _continue true)
          (let _reversed_indices (reverse _indices))
          (while _continue {
            (mut _i nil)
            (if
              (forEach
                _reversed_indices
                (fun (_val) {
                  (set _i _val)
                  (if (!= (@ _indices _i) (+ _i _len (* -1 _r))) stopIteration) }))
              {
                (@= _indices _i (+ 1 (@ _indices _i)))
                (mut _j (+ 1 _i))
                (while (< _j _r) {
                  (@= _indices _j (+ 1 (@ _indices (- _j 1))))
                  (set _j (+ 1 _j)) })
                (if (= stopIteration (_f (select _L _indices)))
                  (set _continue false)) }
              (set _continue false)) }) }) }) }))

# @brief Compute combinations of length _r from a given list, allowing individual elements to be repeated more than once
# @details The original list is not modified.
# @param _L list to get values from
# @param _r number of elements per permutation
# @param _f function to call on each permutation. It can return list:stopIteration to stop iteration early
# =begin
# (let data [0 1 2])
# (list:combinationsWithReplacement data 2 (fun (perm) (print perm)))
# # [0 0]
# # [0 1]
# # [0 2]
# # [1 1]
# # [1 2]
# # [2 2]
# =end
# @author https://github.com/SuperFola
(let combinationsWithReplacement (fun ((ref _L) _r _f) {
  (let _len (len _L))
  (if (and (!= 0 _len) (> _r 0))
    {
      (mut _indices (fill _r 0))
      (if (!= stopIteration (_f (select _L _indices)))
        {
          (mut _continue true)
          (let _reversed_range (iterate (- _r 1) (fun (_x) (- _x 1)) _r))
          (while _continue {
            (mut _i nil)
            (if
              (forEach
                _reversed_range
                (fun (_val) {
                  (set _i _val)
                  (if (!= (@ _indices _i) (- _len 1)) stopIteration) }))
              {
                (mut _j _i)
                (let _val (+ 1 (@ _indices _i)))
                (while (< _j _r) {
                  (@= _indices _j _val)
                  (set _j (+ 1 _j)) })
                (if (= stopIteration (_f (select _L _indices)))
                  (set _continue false)) }
              (set _continue false)) }) }) }) }))

# @brief Compute permutations of length _r from a given list
# @details The original list is not modified.
# @param _L list to get values from
# @param _r number of elements per permutation
# @param _f function to call on each permutation. It can return list:stopIteration to stop iteration early
# =begin
# (let data [0 1 2 3])
# (mut out [])
# (list:permutations data 3 (fun (perm) (append! out perm)))
# (print out)  # length: 24
# # [[0 1 2] [0 1 3] [0 2 1] [0 2 3] [0 3 1] [0 3 2] [1 0 2] [1 0 3] [1 2 0] [1 2 3] [1 3 0] [1 3 2]
# #  [2 0 1] [2 0 3] [2 1 0] [2 1 3] [2 3 0] [2 3 1] [3 0 1] [3 0 2] [3 1 0] [3 1 2] [3 2 0] [3 2 1]]
# =end
# @author https://github.com/SuperFola
(let permutations (fun ((ref _L) _r _f) {
  (let _len (len _L))
  (if (and (<= _r _len) (> _r 0) (> _len 0))
    {
      (let _ind_first_r (iota 0 _r))
      (mut _indices (iota 0 _len))
      (mut _cycles (iterate _len (fun (x) (- x 1)) _r))
      (if (!= stopIteration (_f (select _L _ind_first_r)))
        {
          (mut _continue true)
          (let _reversed_indices (reverse _ind_first_r))
          (while _continue {
            (if
              (not
                (forEach
                  _reversed_indices
                  (fun (_i) {
                    (@= _cycles _i (- (@ _cycles _i) 1))
                    (if (= 0 (@ _cycles _i))
                      {
                        (let _at_i (@ _indices _i))
                        (mut _k _i)
                        (while (< _k _len) {
                          (if (< (+ 1 _k) _len) (@= _indices _k (@ _indices (+ 1 _k))))
                          (set _k (+ 1 _k)) })
                        (@= _indices -1 _at_i)
                        (@= _cycles _i (- _len _i)) }
                      {
                        (let _j (* -1 (@ _cycles _i)))
                        (let _ind_j (@ _indices _j))
                        (@= _indices _j (@ _indices _i))
                        (@= _indices _i _ind_j)
                        (if (= stopIteration (_f (select _L (select _indices _ind_first_r))))
                          (set _continue false))
                        stopIteration }) })))
              (set _continue false)) }) }) }) }))