-- | Used by "Data.Heap" and "Data.PrioHeap".

module Util.Internal.StrictList
    ( List(..)
    , reverse
    ) where

import Prelude hiding (reverse)

import Control.DeepSeq (NFData(..))

-- | A strict list.
data List a = Nil | !a `Cons` !(List a)

infixr 5 `Cons`

instance Functor List where
    fmap :: (a -> b) -> List a -> List b
fmap a -> b
f = List a -> List b
go
      where
        go :: List a -> List b
go List a
Nil = List b
forall a. List a
Nil
        go (a
x `Cons` List a
xs) = a -> b
f a
x b -> List b -> List b
forall a. a -> List a -> List a
`Cons` List a -> List b
go List a
xs
    {-# INLINE fmap #-}

instance Foldable List where
    foldr :: (a -> b -> b) -> b -> List a -> b
foldr a -> b -> b
f b
acc = List a -> b
go
      where
        go :: List a -> b
go List a
Nil = b
acc
        go (a
x `Cons` List a
xs) = a -> b -> b
f a
x (List a -> b
go List a
xs)
    {-# INLINE foldr #-}

instance Traversable List where
    traverse :: (a -> f b) -> List a -> f (List b)
traverse a -> f b
f = List a -> f (List b)
go
      where
        go :: List a -> f (List b)
go List a
Nil = List b -> f (List b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure List b
forall a. List a
Nil
        go (a
x `Cons` List a
xs) = b -> List b -> List b
forall a. a -> List a -> List a
Cons (b -> List b -> List b) -> f b -> f (List b -> List b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x f (List b -> List b) -> f (List b) -> f (List b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> List a -> f (List b)
go List a
xs
    {-# INLINE traverse #-}

instance NFData a => NFData (List a) where
    rnf :: List a -> ()
rnf List a
Nil = ()
    rnf (a
x `Cons` List a
xs) = a -> ()
forall a. NFData a => a -> ()
rnf a
x () -> () -> ()
`seq` List a -> ()
forall a. NFData a => a -> ()
rnf List a
xs

reverse :: List a -> List a
reverse :: List a -> List a
reverse = List a -> List a -> List a
forall a. List a -> List a -> List a
rev List a
forall a. List a
Nil
  where
    rev :: List a -> List a -> List a
rev List a
acc List a
Nil = List a
acc
    rev List a
acc (a
t `Cons` List a
ts) = List a -> List a -> List a
rev (a
t a -> List a -> List a
forall a. a -> List a -> List a
`Cons` List a
acc) List a
ts
{-# INLINE reverse #-}