{-# LANGUAGE OverloadedStrings #-}
{-# OPTIONS_GHC -fno-omit-interface-pragmas #-}
module PlutusTx.List (
    map,
    filter,
    listToMaybe,
    uniqueElement,
    findIndices,
    findIndex,
    foldr,
    reverse,
    zip,
    (++),
    (!!),
    head,
    take,
    tail,
    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 :: (a -> b) -> [a] -> [b]
map a -> b
f [a]
l = case [a]
l of
    []   -> []
    a
x:[a]
xs -> a -> b
f a
x b -> [b] -> [b]
forall a. a -> [a] -> [a]
: (a -> b) -> [a] -> [b]
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 :: (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 ((a -> b -> b) -> b -> [a] -> b
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]
++ :: [a] -> [a] -> [a]
(++) [a]
l [a]
r = (a -> [a] -> [a]) -> [a] -> [a] -> [a]
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 :: (a -> Bool) -> [a] -> [a]
filter a -> Bool
p = (a -> [a] -> [a]) -> [a] -> [a] -> [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr (\a
e [a]
xs -> if a -> Bool
p a
e then a
ea -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs else [a]
xs) []

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

{-# INLINABLE findIndices #-}
-- | Plutus Tx version of 'Data.List.findIndices'.
findIndices :: (a -> Bool) -> [a] -> [Integer]
findIndices :: (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
iInteger -> [Integer] -> [Integer]
forall 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 :: (a -> Bool) -> [a] -> Maybe Integer
findIndex a -> Bool
p [a]
l = [Integer] -> Maybe Integer
forall a. [a] -> Maybe a
listToMaybe ((a -> Bool) -> [a] -> [Integer]
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]
_        !! :: [a] -> Integer -> a
!! Integer
n | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = BuiltinString -> a
forall a. BuiltinString -> a
traceError BuiltinString
negativeIndexError
[]       !! Integer
_ = BuiltinString -> a
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 [a] -> Integer -> a
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 :: [a] -> [a]
reverse [a]
l = [a] -> [a] -> [a]
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
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
a)


{-# INLINABLE zip #-}
-- | Plutus Tx version of 'Data.List.zip'.
zip :: [a] -> [b] -> [(a,b)]
zip :: [a] -> [b] -> [(a, b)]
zip []     [b]
_bs    = []
zip [a]
_as    []     = []
zip (a
a:[a]
as) (b
b:[b]
bs) = (a
a,b
b) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [(a, b)]
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 :: [a] -> a
head []      = BuiltinString -> a
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 :: [a] -> [a]
tail (a
_:[a]
as) =  [a]
as
tail []     =  BuiltinString -> [a]
forall a. BuiltinString -> a
traceError BuiltinString
tailEmptyListError

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

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

{-# INLINABLE elemBy #-}
-- | Plutus Tx version of 'Data.List.elemBy'.
elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
elemBy :: (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
|| (a -> a -> Bool) -> a -> [a] -> 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 :: (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
       | (a -> a -> Bool) -> a -> [a] -> Bool
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 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
nubBy' [a]
ys (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)

{-# INLINABLE zipWith #-}
-- | Plutus Tx version of 'Data.List.zipWith'.
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith :: (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 c -> [c] -> [c]
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 :: (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
_ []          =  []
dropWhile a -> Bool
p xs :: [a]
xs@(a
x:[a]
xs')
    | a -> Bool
p a
x       =  (a -> Bool) -> [a] -> [a]
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 :: (a -> Bool) -> [a] -> ([a], [a])
partition a -> Bool
p [a]
xs = (a -> ([a], [a]) -> ([a], [a])) -> ([a], [a]) -> [a] -> ([a], [a])
forall a b. (a -> b -> b) -> b -> [a] -> b
foldr ((a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
forall a. (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select a -> Bool
p) ([],[]) [a]
xs

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

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

{-# INLINABLE sortBy #-}
-- | Plutus Tx version of 'Data.List.sortBy'.
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy :: (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 Ordering -> Ordering -> Bool
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
aa -> [a] -> [a]
forall 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 Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
GT = a -> [a] -> [a] -> [[a]]
descending a
b (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as) [a]
bs
    descending a
a [a]
as [a]
bs  = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as)[a] -> [[a]] -> [[a]]
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 Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
GT = a -> ([a] -> [a]) -> [a] -> [[a]]
ascending a
b (\[a]
ys -> [a] -> [a]
as (a
aa -> [a] -> [a]
forall 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 [a] -> [[a]] -> [[a]]
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 [a] -> [[a]] -> [[a]]
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 Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
GT = a
ba -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a] -> [a] -> [a]
merge [a]
as  [a]
bs'
      | Bool
otherwise       = a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a] -> [a] -> [a]
merge [a]
as' [a]
bs
    merge [] [a]
bs         = [a]
bs
    merge [a]
as []         = [a]
as