(.module:
  [lux #*
   [control
    functor
    monad
    comonad
    ["." continuation (#+ pending Cont)]
    ["p" parser]]
   [macro (#+ with-gensyms)
    ["." code]
    ["s" syntax (#+ syntax: Syntax)]]
   [data
    bit
    [collection
     [list ("list/." Monad<List>)]]]])

## [Types]
(type: #export (Sequence a)
  {#.doc "An infinite sequence of values."}
  (Cont [a (Sequence a)]))

## [Utils]
(def: (cycle' x xs init full)
  (All [a]
    (-> a (List a) a (List a) (Sequence a)))
  (case xs
    #.Nil           (pending [x (cycle' init full init full)])
    (#.Cons x' xs') (pending [x (cycle' x' xs' init full)])))

## [Functions]
(def: #export (iterate f x)
  {#.doc "Create a sequence by applying a function to a value, and to its result, on and on..."}
  (All [a]
    (-> (-> a a) a (Sequence a)))
  (pending [x (iterate f (f x))]))

(def: #export (repeat x)
  {#.doc "Repeat a value forever."}
  (All [a]
    (-> a (Sequence a)))
  (pending [x (repeat x)]))

(def: #export (cycle xs)
  {#.doc "Go over the elements of a list forever.

          The list should not be empty."}
  (All [a]
    (-> (List a) (Maybe (Sequence a))))
  (case xs
    #.Nil          #.None
    (#.Cons x xs') (#.Some (cycle' x xs' x xs'))))

(do-template [<name> <return> <part>]
  [(def: #export (<name> s)
     (All [a] (-> (Sequence a) <return>))
     (let [[h t] (continuation.run s)]
       <part>))]

  [head a          h]
  [tail (Sequence a) t])

(def: #export (nth idx s)
  (All [a] (-> Nat (Sequence a) a))
  (let [[h t] (continuation.run s)]
    (if (n/> +0 idx)
      (nth (dec idx) t)
      h)))

(do-template [<taker> <dropper> <splitter> <pred-type> <pred-test> <pred-step>]
  [(def: #export (<taker> pred xs)
     (All [a]
       (-> <pred-type> (Sequence a) (List a)))
     (let [[x xs'] (continuation.run xs)]
       (if <pred-test>
         (list& x (<taker> <pred-step> xs'))
         (list))))

   (def: #export (<dropper> pred xs)
     (All [a]
       (-> <pred-type> (Sequence a) (Sequence a)))
     (let [[x xs'] (continuation.run xs)]
       (if <pred-test>
         (<dropper> <pred-step> xs')
         xs)))

   (def: #export (<splitter> pred xs)
     (All [a]
       (-> <pred-type> (Sequence a) [(List a) (Sequence a)]))
     (let [[x xs'] (continuation.run xs)]
       (if <pred-test>
         (let [[tail next] (<splitter> <pred-step> xs')]
           [(#.Cons [x tail]) next])
         [(list) xs])))]
  
  [take-while drop-while split-while (-> a Bit) (pred x)      pred]
  [take       drop       split       Nat        (n/> +0 pred) (dec pred)]
  )

(def: #export (unfold step init)
  {#.doc "A stateful way of infinitely calculating the values of a sequence."}
  (All [a b]
    (-> (-> a [a b]) a (Sequence b)))
  (let [[next x] (step init)]
    (pending [x (unfold step next)])))

(def: #export (filter p xs)
  (All [a] (-> (-> a Bit) (Sequence a) (Sequence a)))
  (let [[x xs'] (continuation.run xs)]
    (if (p x)
      (pending [x (filter p xs')])
      (filter p xs'))))

(def: #export (partition p xs)
  {#.doc "Split a sequence in two based on a predicate.

          The left side contains all entries for which the predicate is #1.

          The right side contains all entries for which the predicate is #0."}
  (All [a] (-> (-> a Bit) (Sequence a) [(Sequence a) (Sequence a)]))
  [(filter p xs) (filter (complement p) xs)])

## [Structures]
(structure: #export _ (Functor Sequence)
  (def: (map f fa)
    (let [[h t] (continuation.run fa)]
      (pending [(f h) (map f t)]))))

(structure: #export _ (CoMonad Sequence)
  (def: functor Functor<Sequence>)
  (def: unwrap head)
  (def: (split wa)
    (let [[head tail] (continuation.run wa)]
      (pending [wa (split tail)]))))

## [Pattern-matching]
(syntax: #export (^sequence& {patterns (s.form (p.many s.any))}
                             body
                             {branches (p.some s.any)})
  {#.doc (doc "Allows destructuring of sequences in pattern-matching expressions."
              "Caveat emptor: Only use it for destructuring, and not for testing values within the sequences."
              (let [(^sequence& x y z _tail) (some-sequence-func 1 2 3)]
                (func x y z)))}
  (with-gensyms [g!sequence]
    (let [body+ (` (let [(~+ (list/join (list/map (function (_ pattern)
                                                    (list (` [(~ pattern) (~ g!sequence)])
                                                          (` ((~! continuation.run) (~ g!sequence)))))
                                                  patterns)))]
                     (~ body)))]
      (wrap (list& g!sequence body+ branches)))))