-- editorconfig-checker-disable-file
{-# LANGUAGE OverloadedStrings #-}
{-# OPTIONS_GHC -fno-omit-interface-pragmas #-}
module PlutusTx.List (
    map,
    filter,
    listToMaybe,
    uniqueElement,
    findIndices,
    findIndex,
    foldr,
    reverse,
    zip,
    (++),
    (!!),
    head,
    tail,
    take,
    drop,
    splitAt,
    nub,
    nubBy,
    zipWith,
    dropWhile,
    partition,
    sort,
    sortBy,
    ) where

import PlutusTx.Bool (Bool (..), otherwise, (||))
import PlutusTx.Builtins (Integer)
import PlutusTx.Builtins qualified as Builtins
import PlutusTx.Eq (Eq, (/=), (==))
import PlutusTx.ErrorCodes
import PlutusTx.Ord (Ord, Ordering (..), compare, (<), (<=))
import PlutusTx.Trace (traceError)
import Prelude (Maybe (..))

{- HLINT ignore -}

{-# INLINABLE map #-}
-- | Plutus Tx version of 'Data.List.map'.
--
--   >>> map (\i -> i + 1) [1, 2, 3]
--   [2,3,4]
--
map :: (a -> b) -> [a] -> [b]
map :: forall a b. (a -> b) -> [a] -> [b]
map a -> b
f [a]
l = case [a]
l of
    []   -> []
    a
x:[a]
xs -> a -> b
f a
x forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
map a -> b
f [a]
xs

{-# INLINABLE foldr #-}
-- | Plutus Tx version of 'Data.List.foldr'.
--
--   >>> foldr (\i s -> s + i) 0 [1, 2, 3, 4]
--   10
--
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr :: forall a b. (a -> b -> b) -> b -> [a] -> b
foldr a -> b -> b
f b
acc [a]
l = case [a]
l of
    []   -> b
acc
    a
x:[a]
xs -> a -> b -> b
f a
x (forall a b. (a -> b -> b) -> b -> [a] -> b
foldr a -> b -> b
f b
acc [a]
xs)

{-# INLINABLE (++) #-}
-- | Plutus Tx version of '(Data.List.++)'.
--
--   >>> [0, 1, 2] ++ [1, 2, 3, 4]
--   [0,1,2,1,2,3,4]
--
infixr 5 ++
(++) :: [a] -> [a] -> [a]
++ :: forall a. [a] -> [a] -> [a]
(++) [a]
l [a]
r = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (:) [a]
r [a]
l

{-# INLINABLE filter #-}
-- | Plutus Tx version of 'Data.List.filter'.
--
--   >>> filter (> 1) [1, 2, 3, 4]
--   [2,3,4]
--
filter :: (a -> Bool) -> [a] -> [a]
filter :: forall a. (a -> Bool) -> [a] -> [a]
filter a -> Bool
p = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\a
e [a]
xs -> if a -> Bool
p a
e then a
eforall a. a -> [a] -> [a]
:[a]
xs else [a]
xs) []

{-# INLINABLE listToMaybe #-}
-- | Plutus Tx version of 'Data.List.listToMaybe'.
listToMaybe :: [a] -> Maybe a
listToMaybe :: forall a. [a] -> Maybe a
listToMaybe []    = forall a. Maybe a
Nothing
listToMaybe (a
x:[a]
_) = forall a. a -> Maybe a
Just a
x

{-# INLINABLE uniqueElement #-}
-- | Return the element in the list, if there is precisely one.
uniqueElement :: [a] -> Maybe a
uniqueElement :: forall a. [a] -> Maybe a
uniqueElement [a
x] = forall a. a -> Maybe a
Just a
x
uniqueElement [a]
_   = forall a. Maybe a
Nothing

{-# INLINABLE findIndices #-}
-- | Plutus Tx version of 'Data.List.findIndices'.
findIndices :: (a -> Bool) -> [a] -> [Integer]
findIndices :: forall a. (a -> Bool) -> [a] -> [Integer]
findIndices a -> Bool
p = Integer -> [a] -> [Integer]
go Integer
0
    where
        go :: Integer -> [a] -> [Integer]
go Integer
i [a]
l = case [a]
l of
            []     -> []
            (a
x:[a]
xs) -> let indices :: [Integer]
indices = Integer -> [a] -> [Integer]
go (Integer -> Integer -> Integer
Builtins.addInteger Integer
i Integer
1) [a]
xs in if a -> Bool
p a
x then Integer
iforall a. a -> [a] -> [a]
:[Integer]
indices else [Integer]
indices

{-# INLINABLE findIndex #-}
-- | Plutus Tx version of 'Data.List.findIndex'.
findIndex :: (a -> Bool) -> [a] -> Maybe Integer
findIndex :: forall a. (a -> Bool) -> [a] -> Maybe Integer
findIndex a -> Bool
p [a]
l = forall a. [a] -> Maybe a
listToMaybe (forall a. (a -> Bool) -> [a] -> [Integer]
findIndices a -> Bool
p [a]
l)

{-# INLINABLE (!!) #-}
-- | Plutus Tx version of '(GHC.List.!!)'.
--
--   >>> [10, 11, 12] !! 2
--   12
--
infixl 9 !!
(!!) :: [a] -> Integer -> a
[a]
_        !! :: forall a. [a] -> Integer -> a
!! Integer
n | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
0 = forall a. BuiltinString -> a
traceError BuiltinString
negativeIndexError
[]       !! Integer
_ = forall a. BuiltinString -> a
traceError BuiltinString
indexTooLargeError
(a
x : [a]
xs) !! Integer
i = if Integer -> Integer -> Bool
Builtins.equalsInteger Integer
i Integer
0
    then a
x
    else [a]
xs forall a. [a] -> Integer -> a
!! Integer -> Integer -> Integer
Builtins.subtractInteger Integer
i Integer
1

{-# INLINABLE reverse #-}
-- | Plutus Tx version of 'Data.List.reverse'.
reverse :: [a] -> [a]
reverse :: forall a. [a] -> [a]
reverse [a]
l = forall a. [a] -> [a] -> [a]
rev [a]
l []
  where
    rev :: [a] -> [a] -> [a]
rev []     [a]
a = [a]
a
    rev (a
x:[a]
xs) [a]
a = [a] -> [a] -> [a]
rev [a]
xs (a
xforall a. a -> [a] -> [a]
:[a]
a)


{-# INLINABLE zip #-}
-- | Plutus Tx version of 'Data.List.zip'.
zip :: [a] -> [b] -> [(a,b)]
zip :: forall a b. [a] -> [b] -> [(a, b)]
zip []     [b]
_bs    = []
zip [a]
_as    []     = []
zip (a
a:[a]
as) (b
b:[b]
bs) = (a
a,b
b) forall a. a -> [a] -> [a]
: forall a b. [a] -> [b] -> [(a, b)]
zip [a]
as [b]
bs

{-# INLINABLE head #-}
-- | Plutus Tx version of 'Data.List.head'.
head :: [a] -> a
head :: forall a. [a] -> a
head []      = forall a. BuiltinString -> a
traceError BuiltinString
headEmptyListError
head (a
x : [a]
_) = a
x

{-# INLINABLE tail #-}
-- | Plutus Tx version of 'Data.List.tail'.
tail :: [a] -> [a]
tail :: forall a. [a] -> [a]
tail (a
_:[a]
as) =  [a]
as
tail []     =  forall a. BuiltinString -> a
traceError BuiltinString
tailEmptyListError

{-# INLINABLE take #-}
-- | Plutus Tx version of 'Data.List.take'.
take :: Integer -> [a] -> [a]
take :: forall a. Integer -> [a] -> [a]
take Integer
n [a]
_      | Integer
n forall a. Ord a => a -> a -> Bool
<= Integer
0 =  []
take Integer
_ []              =  []
take Integer
n (a
x:[a]
xs)          =  a
x forall a. a -> [a] -> [a]
: forall a. Integer -> [a] -> [a]
take (Integer -> Integer -> Integer
Builtins.subtractInteger Integer
n Integer
1) [a]
xs

{-# INLINABLE drop #-}
-- | Plutus Tx version of 'Data.List.drop'.
drop :: Integer -> [a] -> [a]
drop :: forall a. Integer -> [a] -> [a]
drop Integer
n [a]
xs     | Integer
n forall a. Ord a => a -> a -> Bool
<= Integer
0 = [a]
xs
drop Integer
_ []              = []
drop Integer
n (a
_:[a]
xs)          = forall a. Integer -> [a] -> [a]
drop (Integer -> Integer -> Integer
Builtins.subtractInteger Integer
n Integer
1) [a]
xs

{-# INLINABLE splitAt #-}
-- | Plutus Tx version of 'Data.List.splitAt'.
splitAt :: Integer -> [a] -> ([a], [a])
splitAt :: forall a. Integer -> [a] -> ([a], [a])
splitAt Integer
n [a]
xs
  | Integer
n forall a. Ord a => a -> a -> Bool
<= Integer
0    = ([], [a]
xs)
  | Bool
otherwise = forall a. Integer -> [a] -> ([a], [a])
go Integer
n [a]
xs
  where
    go :: Integer -> [a] -> ([a], [a])
    go :: forall a. Integer -> [a] -> ([a], [a])
go Integer
_ []     = ([], [])
    go Integer
m (a
y:[a]
ys)
      | Integer
m forall a. Eq a => a -> a -> Bool
== Integer
1 = ([a
y], [a]
ys)
      | Bool
otherwise = case forall a. Integer -> [a] -> ([a], [a])
go (Integer -> Integer -> Integer
Builtins.subtractInteger Integer
m Integer
1) [a]
ys of
          ([a]
zs, [a]
ws) -> (a
yforall a. a -> [a] -> [a]
:[a]
zs, [a]
ws)

{-# INLINABLE nub #-}
-- | Plutus Tx version of 'Data.List.nub'.
nub :: (Eq a) => [a] -> [a]
nub :: forall a. Eq a => [a] -> [a]
nub =  forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy forall a. Eq a => a -> a -> Bool
(==)

{-# INLINABLE elemBy #-}
-- | Plutus Tx version of 'Data.List.elemBy'.
elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
elemBy :: forall a. (a -> a -> Bool) -> a -> [a] -> Bool
elemBy a -> a -> Bool
_  a
_ []     =  Bool
False
elemBy a -> a -> Bool
eq a
y (a
x:[a]
xs) =  a
x a -> a -> Bool
`eq` a
y Bool -> Bool -> Bool
|| forall a. (a -> a -> Bool) -> a -> [a] -> Bool
elemBy a -> a -> Bool
eq a
y [a]
xs

{-# INLINABLE nubBy #-}
-- | Plutus Tx version of 'Data.List.nubBy'.
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy :: forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy a -> a -> Bool
eq [a]
l = [a] -> [a] -> [a]
nubBy' [a]
l []
  where
    nubBy' :: [a] -> [a] -> [a]
nubBy' [] [a]
_         = []
    nubBy' (a
y:[a]
ys) [a]
xs
       | forall a. (a -> a -> Bool) -> a -> [a] -> Bool
elemBy a -> a -> Bool
eq a
y [a]
xs = [a] -> [a] -> [a]
nubBy' [a]
ys [a]
xs
       | Bool
otherwise      = a
y forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
nubBy' [a]
ys (a
yforall a. a -> [a] -> [a]
:[a]
xs)

{-# INLINABLE zipWith #-}
-- | Plutus Tx version of 'Data.List.zipWith'.
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> b -> c
f = [a] -> [b] -> [c]
go
  where
    go :: [a] -> [b] -> [c]
go [] [b]
_          = []
    go [a]
_ []          = []
    go (a
x:[a]
xs) (b
y:[b]
ys) = a -> b -> c
f a
x b
y forall a. a -> [a] -> [a]
: [a] -> [b] -> [c]
go [a]
xs [b]
ys

{-# INLINABLE dropWhile #-}
-- | Plutus Tx version of 'Data.List.dropWhile'.
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
_ []          =  []
dropWhile a -> Bool
p xs :: [a]
xs@(a
x:[a]
xs')
    | a -> Bool
p a
x       =  forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
p [a]
xs'
    | Bool
otherwise =  [a]
xs

{-# INLINABLE partition #-}
-- | Plutus Tx version of 'Data.List.partition'.
partition :: (a -> Bool) -> [a] -> ([a],[a])
partition :: forall a. (a -> Bool) -> [a] -> ([a], [a])
partition a -> Bool
p [a]
xs = forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (forall a. (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select a -> Bool
p) ([],[]) [a]
xs

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select :: forall a. (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select a -> Bool
p a
x ~([a]
ts,[a]
fs) | a -> Bool
p a
x       = (a
xforall a. a -> [a] -> [a]
:[a]
ts,[a]
fs)
                    | Bool
otherwise = ([a]
ts, a
xforall a. a -> [a] -> [a]
:[a]
fs)

{-# INLINABLE sort #-}
-- | Plutus Tx version of 'Data.List.sort'.
sort :: Ord a => [a] -> [a]
sort :: forall a. Ord a => [a] -> [a]
sort = forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy forall a. Ord a => a -> a -> Ordering
compare

{-# INLINABLE sortBy #-}
-- | Plutus Tx version of 'Data.List.sortBy'.
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
cmp [a]
l = [[a]] -> [a]
mergeAll ([a] -> [[a]]
sequences [a]
l)
  where
    sequences :: [a] -> [[a]]
sequences (a
a:a
b:[a]
xs)
      | a
a a -> a -> Ordering
`cmp` a
b forall a. Eq a => a -> a -> Bool
== Ordering
GT = a -> [a] -> [a] -> [[a]]
descending a
b [a
a]  [a]
xs
      | Bool
otherwise       = a -> ([a] -> [a]) -> [a] -> [[a]]
ascending  a
b (a
aforall a. a -> [a] -> [a]
:) [a]
xs
    sequences [a]
xs = [[a]
xs]

    descending :: a -> [a] -> [a] -> [[a]]
descending a
a [a]
as (a
b:[a]
bs)
      | a
a a -> a -> Ordering
`cmp` a
b forall a. Eq a => a -> a -> Bool
== Ordering
GT = a -> [a] -> [a] -> [[a]]
descending a
b (a
aforall a. a -> [a] -> [a]
:[a]
as) [a]
bs
    descending a
a [a]
as [a]
bs  = (a
aforall a. a -> [a] -> [a]
:[a]
as)forall a. a -> [a] -> [a]
: [a] -> [[a]]
sequences [a]
bs

    ascending :: a -> ([a] -> [a]) -> [a] -> [[a]]
ascending a
a [a] -> [a]
as (a
b:[a]
bs)
      | a
a a -> a -> Ordering
`cmp` a
b forall a. Eq a => a -> a -> Bool
/= Ordering
GT = a -> ([a] -> [a]) -> [a] -> [[a]]
ascending a
b (\[a]
ys -> [a] -> [a]
as (a
aforall a. a -> [a] -> [a]
:[a]
ys)) [a]
bs
    ascending a
a [a] -> [a]
as [a]
bs   = let x :: [a]
x = [a] -> [a]
as [a
a]
                          in [a]
x forall a. a -> [a] -> [a]
: [a] -> [[a]]
sequences [a]
bs

    mergeAll :: [[a]] -> [a]
mergeAll [[a]
x] = [a]
x
    mergeAll [[a]]
xs  = [[a]] -> [a]
mergeAll ([[a]] -> [[a]]
mergePairs [[a]]
xs)

    mergePairs :: [[a]] -> [[a]]
mergePairs ([a]
a:[a]
b:[[a]]
xs) = let x :: [a]
x = [a] -> [a] -> [a]
merge [a]
a [a]
b
                          in [a]
x forall a. a -> [a] -> [a]
: [[a]] -> [[a]]
mergePairs [[a]]
xs
    mergePairs [[a]]
xs       = [[a]]
xs

    merge :: [a] -> [a] -> [a]
merge as :: [a]
as@(a
a:[a]
as') bs :: [a]
bs@(a
b:[a]
bs')
      | a
a a -> a -> Ordering
`cmp` a
b forall a. Eq a => a -> a -> Bool
== Ordering
GT = a
bforall a. a -> [a] -> [a]
:[a] -> [a] -> [a]
merge [a]
as  [a]
bs'
      | Bool
otherwise       = a
aforall a. a -> [a] -> [a]
:[a] -> [a] -> [a]
merge [a]
as' [a]
bs
    merge [] [a]
bs         = [a]
bs
    merge [a]
as []         = [a]
as