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


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

concat :: ([] ([] a1)) -> [] a1
concat l =
  case l of {
   [] -> [];
   (:) x xs -> (Prelude.++) x (concat xs)}

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}}}

listToMaybe :: ([] a1) -> Prelude.Maybe ([] a1)
listToMaybe xs =
  case xs of {
   [] -> Prelude.Nothing;
   (:) a l -> Prelude.Just xs}

olast :: ([] a1) -> Prelude.Maybe a1
olast l =
  let {
   go res xs =
     case xs of {
      [] -> res;
      (:) x xs0 -> go (Prelude.Just x) xs0}}
  in go Prelude.Nothing l

forFold :: a2 -> ([] a1) -> (a2 -> a1 -> a2) -> a2
forFold b v f =
  Data.List.foldl' 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)}