{-# LANGUAGE DerivingStrategies    #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TemplateHaskell       #-}

module PlutusTx.Data.List (
    -- constructor exported for testing
    List(List),
    append,
    find,
    findIndices,
    filter,
    mapMaybe,
    any,
    foldMap,
    map,
    length,
    mconcat,
    fromSOP,
    toSOP,
) where

import PlutusTx.Builtins qualified as B
import PlutusTx.Builtins.Internal (BuiltinList)
import PlutusTx.Builtins.Internal qualified as BI
import PlutusTx.IsData.Class (FromData (..), ToData (..), UnsafeFromData (..))
import PlutusTx.Lift (makeLift)
import PlutusTx.Prelude hiding (any, filter, find, findIndices, foldMap, length, map, mapMaybe,
                         mconcat, pred)
import Prettyprinter (Pretty (..))

import Data.Semigroup qualified as Haskell
import Prelude qualified as Haskell

-- | A list type backed directly by 'Data'. It is meant to be used whenever fast
-- encoding/decoding to/from 'Data' is needed.
newtype List a = List (BuiltinList BuiltinData)
  deriving stock (Int -> List a -> ShowS
[List a] -> ShowS
List a -> String
(Int -> List a -> ShowS)
-> (List a -> String) -> ([List a] -> ShowS) -> Show (List a)
forall a. Int -> List a -> ShowS
forall a. [List a] -> ShowS
forall a. List a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Int -> List a -> ShowS
showsPrec :: Int -> List a -> ShowS
$cshow :: forall a. List a -> String
show :: List a -> String
$cshowList :: forall a. [List a] -> ShowS
showList :: [List a] -> ShowS
Haskell.Show, List a -> List a -> Bool
(List a -> List a -> Bool)
-> (List a -> List a -> Bool) -> Eq (List a)
forall a. List a -> List a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. List a -> List a -> Bool
== :: List a -> List a -> Bool
$c/= :: forall a. List a -> List a -> Bool
/= :: List a -> List a -> Bool
Haskell.Eq)

instance Eq (List a) where
    {-# INLINEABLE (==) #-}
    List BuiltinList BuiltinData
l == :: List a -> List a -> Bool
== List BuiltinList BuiltinData
l' =
        case (BuiltinList BuiltinData
-> Maybe (BuiltinData, BuiltinList BuiltinData)
forall a. BuiltinList a -> Maybe (a, BuiltinList a)
B.uncons BuiltinList BuiltinData
l, BuiltinList BuiltinData
-> Maybe (BuiltinData, BuiltinList BuiltinData)
forall a. BuiltinList a -> Maybe (a, BuiltinList a)
B.uncons BuiltinList BuiltinData
l') of
            (Just (BuiltinData
h, BuiltinList BuiltinData
t), Just (BuiltinData
h', BuiltinList BuiltinData
t')) -> BuiltinData
h BuiltinData -> BuiltinData -> Bool
forall a. Eq a => a -> a -> Bool
== BuiltinData
h' Bool -> Bool -> Bool
&& BuiltinList BuiltinData -> List Any
forall a. BuiltinList BuiltinData -> List a
List BuiltinList BuiltinData
t List Any -> List Any -> Bool
forall a. Eq a => a -> a -> Bool
== BuiltinList BuiltinData -> List Any
forall a. BuiltinList BuiltinData -> List a
List BuiltinList BuiltinData
t'
            (Maybe (BuiltinData, BuiltinList BuiltinData)
Nothing, Maybe (BuiltinData, BuiltinList BuiltinData)
Nothing)           -> Bool
True
            (Maybe (BuiltinData, BuiltinList BuiltinData),
 Maybe (BuiltinData, BuiltinList BuiltinData))
_                            -> Bool
False

instance ToData (List a) where
    {-# INLINEABLE toBuiltinData #-}
    toBuiltinData :: List a -> BuiltinData
toBuiltinData (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> BuiltinData
BI.mkList BuiltinList BuiltinData
l

instance FromData (List a) where
    {-# INLINEABLE fromBuiltinData #-}
    fromBuiltinData :: BuiltinData -> Maybe (List a)
fromBuiltinData = List a -> Maybe (List a)
forall a. a -> Maybe a
Just (List a -> Maybe (List a))
-> (BuiltinData -> List a) -> BuiltinData -> Maybe (List a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List (BuiltinList BuiltinData -> List a)
-> (BuiltinData -> BuiltinList BuiltinData)
-> BuiltinData
-> List a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BuiltinData -> BuiltinList BuiltinData
BI.unsafeDataAsList

instance UnsafeFromData (List a) where
    {-# INLINEABLE unsafeFromBuiltinData #-}
    unsafeFromBuiltinData :: BuiltinData -> List a
unsafeFromBuiltinData = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List (BuiltinList BuiltinData -> List a)
-> (BuiltinData -> BuiltinList BuiltinData)
-> BuiltinData
-> List a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BuiltinData -> BuiltinList BuiltinData
BI.unsafeDataAsList

instance (UnsafeFromData a, Pretty a) => Pretty (List a) where
    {-# INLINEABLE pretty #-}
    pretty :: forall ann. List a -> Doc ann
pretty = [a] -> Doc ann
forall ann. [a] -> Doc ann
forall a ann. Pretty a => a -> Doc ann
pretty ([a] -> Doc ann) -> (List a -> [a]) -> List a -> Doc ann
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List a -> [a]
forall a. UnsafeFromData a => List a -> [a]
toSOP

{-# INLINEABLE cons #-}
cons :: (ToData a) => a -> List a -> List a
cons :: forall a. ToData a => a -> List a -> List a
cons a
h (List BuiltinList BuiltinData
t) = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List (BuiltinData -> BuiltinList BuiltinData -> BuiltinList BuiltinData
forall a. a -> BuiltinList a -> BuiltinList a
BI.mkCons (a -> BuiltinData
forall a. ToData a => a -> BuiltinData
toBuiltinData a
h) BuiltinList BuiltinData
t)

{-# INLINEABLE append #-}

append :: List a -> List a -> List a
append :: forall a. List a -> List a -> List a
append (List BuiltinList BuiltinData
l) (List BuiltinList BuiltinData
l') = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List (BuiltinList BuiltinData -> BuiltinList BuiltinData
go BuiltinList BuiltinData
l)
  where
    go :: BuiltinList BuiltinData -> BuiltinList BuiltinData
go =
        BuiltinList BuiltinData
-> (BuiltinData
    -> BuiltinList BuiltinData -> BuiltinList BuiltinData)
-> BuiltinList BuiltinData
-> BuiltinList BuiltinData
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            BuiltinList BuiltinData
l'
            (\BuiltinData
h BuiltinList BuiltinData
t -> BuiltinData -> BuiltinList BuiltinData -> BuiltinList BuiltinData
forall a. a -> BuiltinList a -> BuiltinList a
BI.mkCons BuiltinData
h (BuiltinList BuiltinData -> BuiltinList BuiltinData
go BuiltinList BuiltinData
t))

instance Semigroup (List a) where
    <> :: List a -> List a -> List a
(<>) = List a -> List a -> List a
forall a. List a -> List a -> List a
append

instance Monoid (List a) where
    mempty :: List a
mempty = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List BuiltinList BuiltinData
forall arep. MkNil arep => BuiltinList arep
B.mkNil

instance Haskell.Semigroup  (List a) where
    <> :: List a -> List a -> List a
(<>) = List a -> List a -> List a
forall a. List a -> List a -> List a
append

instance Haskell.Monoid (List a) where
    mempty :: List a
mempty = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List BuiltinList BuiltinData
forall arep. MkNil arep => BuiltinList arep
B.mkNil

{-# INLINEABLE toSOP #-}
toSOP :: (UnsafeFromData a) => List a -> [a]
toSOP :: forall a. UnsafeFromData a => List a -> [a]
toSOP (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> [a]
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> [a]
go = [a]
-> (BuiltinData -> BuiltinList BuiltinData -> [a])
-> BuiltinList BuiltinData
-> [a]
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList' [] (\BuiltinData
h BuiltinList BuiltinData
t -> BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h a -> [a] -> [a]
forall a. a -> [a] -> [a]
: BuiltinList BuiltinData -> [a]
go BuiltinList BuiltinData
t)

{-# INLINEABLE fromSOP #-}
fromSOP :: (ToData a) => [a] -> List a
fromSOP :: forall a. ToData a => [a] -> List a
fromSOP = BuiltinList BuiltinData -> List a
forall a. BuiltinList BuiltinData -> List a
List (BuiltinList BuiltinData -> List a)
-> ([a] -> BuiltinList BuiltinData) -> [a] -> List a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BuiltinData -> BuiltinList BuiltinData
BI.unsafeDataAsList (BuiltinData -> BuiltinList BuiltinData)
-> ([a] -> BuiltinData) -> [a] -> BuiltinList BuiltinData
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [BuiltinData] -> BuiltinData
B.mkList ([BuiltinData] -> BuiltinData)
-> ([a] -> [BuiltinData]) -> [a] -> BuiltinData
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> BuiltinData) -> [a] -> [BuiltinData]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> BuiltinData
forall a. ToData a => a -> BuiltinData
toBuiltinData

{-# INLINEABLE find #-}
find :: (UnsafeFromData a) => (a -> Bool) -> List a -> Maybe a
find :: forall a. UnsafeFromData a => (a -> Bool) -> List a -> Maybe a
find a -> Bool
pred' (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> Maybe a
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> Maybe a
go =
        Maybe a
-> (BuiltinData -> BuiltinList BuiltinData -> Maybe a)
-> BuiltinList BuiltinData
-> Maybe a
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            Maybe a
forall a. Maybe a
Nothing
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in
                    if a -> Bool
pred' a
h'
                        then a -> Maybe a
forall a. a -> Maybe a
Just a
h'
                        else BuiltinList BuiltinData -> Maybe a
go BuiltinList BuiltinData
t
            )

{-# INLINEABLE findIndices #-}
findIndices :: (UnsafeFromData a) => (a -> Bool) -> List a -> List Integer
findIndices :: forall a. UnsafeFromData a => (a -> Bool) -> List a -> List Integer
findIndices a -> Bool
pred' (List BuiltinList BuiltinData
l) = Integer -> BuiltinList BuiltinData -> List Integer
go Integer
0 BuiltinList BuiltinData
l
  where
    go :: Integer -> BuiltinList BuiltinData -> List Integer
go Integer
i =
        List Integer
-> (BuiltinData -> BuiltinList BuiltinData -> List Integer)
-> BuiltinList BuiltinData
-> List Integer
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            List Integer
forall a. Monoid a => a
mempty
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                    indices :: List Integer
indices = Integer -> BuiltinList BuiltinData -> List Integer
go (Integer -> Integer -> Integer
B.addInteger Integer
1 Integer
i) BuiltinList BuiltinData
t
                in
                    if a -> Bool
pred' a
h'
                        then Integer
i Integer -> List Integer -> List Integer
forall a. ToData a => a -> List a -> List a
`cons` List Integer
indices
                        else List Integer
indices
            )

{-# INLINEABLE filter #-}
filter :: (UnsafeFromData a, ToData a) => (a -> Bool) -> List a -> List a
filter :: forall a.
(UnsafeFromData a, ToData a) =>
(a -> Bool) -> List a -> List a
filter a -> Bool
pred (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> List a
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> List a
go =
        List a
-> (BuiltinData -> BuiltinList BuiltinData -> List a)
-> BuiltinList BuiltinData
-> List a
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            List a
forall a. Monoid a => a
mempty
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in if a -> Bool
pred a
h' then a
h' a -> List a -> List a
forall a. ToData a => a -> List a -> List a
`cons` BuiltinList BuiltinData -> List a
go BuiltinList BuiltinData
t else BuiltinList BuiltinData -> List a
go BuiltinList BuiltinData
t
            )

{-# INLINEABLE mapMaybe #-}
mapMaybe :: (UnsafeFromData a, ToData b) => (a -> Maybe b) -> List a -> List b
mapMaybe :: forall a b.
(UnsafeFromData a, ToData b) =>
(a -> Maybe b) -> List a -> List b
mapMaybe a -> Maybe b
f (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> List b
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> List b
go =
        List b
-> (BuiltinData -> BuiltinList BuiltinData -> List b)
-> BuiltinList BuiltinData
-> List b
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            List b
forall a. Monoid a => a
mempty
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in case a -> Maybe b
f a
h' of
                    Just b
b  -> b
b b -> List b -> List b
forall a. ToData a => a -> List a -> List a
`cons` BuiltinList BuiltinData -> List b
go BuiltinList BuiltinData
t
                    Maybe b
Nothing -> BuiltinList BuiltinData -> List b
go BuiltinList BuiltinData
t
            )

{-# INLINEABLE any #-}
any :: (UnsafeFromData a) => (a -> Bool) -> List a -> Bool
any :: forall a. UnsafeFromData a => (a -> Bool) -> List a -> Bool
any a -> Bool
pred (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> Bool
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> Bool
go =
        Bool
-> (BuiltinData -> BuiltinList BuiltinData -> Bool)
-> BuiltinList BuiltinData
-> Bool
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            Bool
False
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in a -> Bool
pred a
h' Bool -> Bool -> Bool
|| BuiltinList BuiltinData -> Bool
go BuiltinList BuiltinData
t
            )

{-# INLINEABLE foldMap #-}
foldMap :: (UnsafeFromData a, Monoid m) => (a -> m) -> List a -> m
foldMap :: forall a m. (UnsafeFromData a, Monoid m) => (a -> m) -> List a -> m
foldMap a -> m
f (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> m
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> m
go =
        m
-> (BuiltinData -> BuiltinList BuiltinData -> m)
-> BuiltinList BuiltinData
-> m
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            m
forall a. Monoid a => a
mempty
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in a -> m
f a
h' m -> m -> m
forall a. Semigroup a => a -> a -> a
<> BuiltinList BuiltinData -> m
go BuiltinList BuiltinData
t
            )
{-# INLINEABLE map #-}
map :: (UnsafeFromData a, ToData b) => (a -> b) -> List a -> List b
map :: forall a b.
(UnsafeFromData a, ToData b) =>
(a -> b) -> List a -> List b
map a -> b
f (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> List b
forall a. BuiltinList BuiltinData -> List a
List (BuiltinList BuiltinData -> BuiltinList BuiltinData
go BuiltinList BuiltinData
l)
  where
    go :: BuiltinList BuiltinData -> BuiltinList BuiltinData
go =
        BuiltinList BuiltinData
-> (BuiltinData
    -> BuiltinList BuiltinData -> BuiltinList BuiltinData)
-> BuiltinList BuiltinData
-> BuiltinList BuiltinData
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            BuiltinList BuiltinData
forall arep. MkNil arep => BuiltinList arep
B.mkNil
            (\BuiltinData
h BuiltinList BuiltinData
t -> BuiltinData -> BuiltinList BuiltinData -> BuiltinList BuiltinData
forall a. a -> BuiltinList a -> BuiltinList a
BI.mkCons (b -> BuiltinData
forall a. ToData a => a -> BuiltinData
toBuiltinData (b -> BuiltinData) -> b -> BuiltinData
forall a b. (a -> b) -> a -> b
$ a -> b
f (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
$ BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h) (BuiltinList BuiltinData -> BuiltinList BuiltinData
go BuiltinList BuiltinData
t))

{-# INLINEABLE length #-}
length :: List a -> Integer
length :: forall a. List a -> Integer
length (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> Integer -> Integer
forall {a}. BuiltinList a -> Integer -> Integer
go BuiltinList BuiltinData
l Integer
0
  where
    go :: BuiltinList a -> Integer -> Integer
go =
        (Integer -> Integer)
-> (a -> BuiltinList a -> Integer -> Integer)
-> BuiltinList a
-> Integer
-> Integer
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            Integer -> Integer
forall a. a -> a
id
            (\a
_ BuiltinList a
t -> Integer -> Integer -> Integer
B.addInteger Integer
1 (Integer -> Integer) -> (Integer -> Integer) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BuiltinList a -> Integer -> Integer
go BuiltinList a
t)

{-# INLINABLE mconcat #-}
-- | Plutus Tx version of 'Data.Monoid.mconcat'.
mconcat :: (Monoid a, UnsafeFromData a) => List a -> a
mconcat :: forall a. (Monoid a, UnsafeFromData a) => List a -> a
mconcat (List BuiltinList BuiltinData
l) = BuiltinList BuiltinData -> a
go BuiltinList BuiltinData
l
  where
    go :: BuiltinList BuiltinData -> a
go =
        a
-> (BuiltinData -> BuiltinList BuiltinData -> a)
-> BuiltinList BuiltinData
-> a
forall a r. r -> (a -> BuiltinList a -> r) -> BuiltinList a -> r
B.caseList'
            a
forall a. Monoid a => a
mempty
            (\BuiltinData
h BuiltinList BuiltinData
t ->
                let h' :: a
h' = BuiltinData -> a
forall a. UnsafeFromData a => BuiltinData -> a
unsafeFromBuiltinData BuiltinData
h
                in a
h' a -> a -> a
forall a. Semigroup a => a -> a -> a
<> BuiltinList BuiltinData -> a
go BuiltinList BuiltinData
t
            )

makeLift ''List