module LinearScan.List1 where


import Debug.Trace (trace, traceShow, traceShowId)
import qualified Prelude
import qualified Data.IntMap
import qualified Data.IntSet
import qualified Data.List
import qualified Data.Ord
import qualified Data.Functor.Identity
import qualified Hask.Utils

import qualified LinearScan.Eqtype as Eqtype
import qualified LinearScan.Seq as Seq


__ :: any
__ = Prelude.error "Logical or arity value used"

concat :: ([] ([] a1)) -> [] a1
concat =
  Seq.flatten

maybeLookup :: Eqtype.Equality__Coq_type -> ([]
               ((,) Eqtype.Equality__Coq_sort a1)) ->
               Eqtype.Equality__Coq_sort -> Prelude.Maybe a1
maybeLookup a v x =
  case v of {
   [] -> Prelude.Nothing;
   (:) p xs ->
    case p of {
     (,) k v0 ->
      case Eqtype.eq_op a k x of {
       Prelude.True -> Prelude.Just v0;
       Prelude.False -> maybeLookup a xs x}}}

forFold :: a2 -> ([] a1) -> (a2 -> a1 -> a2) -> a2
forFold b v f =
  Data.List.foldl' f b v

forFoldr :: a2 -> ([] a1) -> (a1 -> a2 -> a2) -> a2
forFoldr b v f =
  Prelude.foldr f b v

catMaybes :: ([] (Prelude.Maybe a1)) -> [] a1
catMaybes l =
  let {
   f = \mx rest ->
    case mx of {
     Prelude.Just x -> (:) x rest;
     Prelude.Nothing -> rest}}
  in
  Prelude.foldr f [] l

span :: (a1 -> Prelude.Bool) -> ([] a1) -> (,) ([] a1) ([] a1)
span p l =
  case l of {
   [] -> (,) [] [];
   (:) x xs ->
    case p x of {
     Prelude.True ->
      case span p xs of {
       (,) ys zs -> (,) ((:) x ys) zs};
     Prelude.False -> (,) [] l}}

partition :: (a1 -> Prelude.Bool) -> ([] a1) -> (,) ([] a1) ([] a1)
partition p =
  Prelude.foldr (\x acc ->
    case p x of {
     Prelude.True -> (,) ((:) x (Prelude.fst acc)) (Prelude.snd acc);
     Prelude.False -> (,) (Prelude.fst acc) ((:) x (Prelude.snd acc))}) ((,)
    [] [])

insert :: (a1 -> a1 -> Prelude.Bool) -> a1 -> ([] a1) -> [] a1
insert p z l =
  case l of {
   [] -> (:) z [];
   (:) x xs ->
    case p x z of {
     Prelude.True -> (:) x (insert p z xs);
     Prelude.False -> (:) z ((:) x xs)}}

sortBy :: (a1 -> a1 -> Prelude.Bool) -> ([] a1) -> [] a1
sortBy p l =
  case l of {
   [] -> [];
   (:) x xs -> insert p x (sortBy p xs)}