module LinearScan.List1 where


import Debug.Trace (trace, traceShow)
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 LinearScan.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}}}

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

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

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

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