{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DeriveFoldable        #-}
{-# LANGUAGE DeriveFunctor         #-}
{-# LANGUAGE DeriveTraversable     #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE InstanceSigs          #-}
{-# LANGUAGE KindSignatures        #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE Safe                  #-}
{-# LANGUAGE ScopedTypeVariables   #-}
module Data.RAList.NonEmpty.Internal (
    NERAList (..),
    NERAList' (..),
    -- * Showing
    explicitShow,
    explicitShowsPrec,
    -- * Construction
    singleton,
    cons,
    -- * Indexing
    (!),
    (!?),
    head,
    last,
    length,
    null,
    -- * Conversions
    toNonEmpty,
    toList,
    fromNonEmpty,
    -- * Folding
    foldMap1,
    foldr1Map,
    ifoldMap,
    ifoldMap1,
    ifoldr1Map,
    -- * Mapping
    adjust,
    map,
    imap,
    itraverse,
#ifdef MIN_VERSION_semigroupoids
    itraverse1,
#endif
    ) where

import Prelude
       (Bool (..), Eq, Functor (..), Int, Maybe, Num (..), Ord (..), Show (..),
       ShowS, String, otherwise, seq, showParen, showString, ($), (.))

import Control.Applicative (Applicative (..), (<$>))
import Control.DeepSeq     (NFData (..))
import Control.Exception   (ArrayException (IndexOutOfBounds), throw)
import Data.Boring         (Absurd (..))
import Data.Hashable       (Hashable (..))
import Data.List.NonEmpty  (NonEmpty (..))
import Data.Maybe          (fromMaybe)
import Data.Monoid         (Monoid (..))
import Data.Semigroup      (Semigroup (..))

import qualified Data.Foldable      as I (Foldable (..))
import qualified Data.List.NonEmpty as NEList
import qualified Data.Traversable   as I (Traversable (..))
import qualified Test.QuickCheck    as QC

import qualified Data.Foldable.WithIndex    as WI (FoldableWithIndex (..))
import qualified Data.Functor.WithIndex     as WI (FunctorWithIndex (..))
import qualified Data.Traversable.WithIndex as WI (TraversableWithIndex (..))

#ifdef MIN_VERSION_semigroupoids
import Data.Functor.Apply (Apply (..))

import qualified Data.Semigroup.Foldable    as I (Foldable1 (..))
import qualified Data.Semigroup.Traversable as I (Traversable1 (..))
#endif

import qualified Data.RAList.Tree.Internal as Tr

import Data.RAList.Tree (Leaf (..), Node (..))

-- $setup
-- >>> import Data.Char (toUpper)

-------------------------------------------------------------------------------
-- Type
-------------------------------------------------------------------------------

-- | Non-empty random access list.
newtype NERAList a = NE (NERAList' Leaf a)
  deriving (NERAList a -> NERAList a -> Bool
(NERAList a -> NERAList a -> Bool)
-> (NERAList a -> NERAList a -> Bool) -> Eq (NERAList a)
forall a. Eq a => NERAList a -> NERAList a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => NERAList a -> NERAList a -> Bool
== :: NERAList a -> NERAList a -> Bool
$c/= :: forall a. Eq a => NERAList a -> NERAList a -> Bool
/= :: NERAList a -> NERAList a -> Bool
Eq, Eq (NERAList a)
Eq (NERAList a) =>
(NERAList a -> NERAList a -> Ordering)
-> (NERAList a -> NERAList a -> Bool)
-> (NERAList a -> NERAList a -> Bool)
-> (NERAList a -> NERAList a -> Bool)
-> (NERAList a -> NERAList a -> Bool)
-> (NERAList a -> NERAList a -> NERAList a)
-> (NERAList a -> NERAList a -> NERAList a)
-> Ord (NERAList a)
NERAList a -> NERAList a -> Bool
NERAList a -> NERAList a -> Ordering
NERAList a -> NERAList a -> NERAList a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (NERAList a)
forall a. Ord a => NERAList a -> NERAList a -> Bool
forall a. Ord a => NERAList a -> NERAList a -> Ordering
forall a. Ord a => NERAList a -> NERAList a -> NERAList a
$ccompare :: forall a. Ord a => NERAList a -> NERAList a -> Ordering
compare :: NERAList a -> NERAList a -> Ordering
$c< :: forall a. Ord a => NERAList a -> NERAList a -> Bool
< :: NERAList a -> NERAList a -> Bool
$c<= :: forall a. Ord a => NERAList a -> NERAList a -> Bool
<= :: NERAList a -> NERAList a -> Bool
$c> :: forall a. Ord a => NERAList a -> NERAList a -> Bool
> :: NERAList a -> NERAList a -> Bool
$c>= :: forall a. Ord a => NERAList a -> NERAList a -> Bool
>= :: NERAList a -> NERAList a -> Bool
$cmax :: forall a. Ord a => NERAList a -> NERAList a -> NERAList a
max :: NERAList a -> NERAList a -> NERAList a
$cmin :: forall a. Ord a => NERAList a -> NERAList a -> NERAList a
min :: NERAList a -> NERAList a -> NERAList a
Ord, (forall a b. (a -> b) -> NERAList a -> NERAList b)
-> (forall a b. a -> NERAList b -> NERAList a) -> Functor NERAList
forall a b. a -> NERAList b -> NERAList a
forall a b. (a -> b) -> NERAList a -> NERAList b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> NERAList a -> NERAList b
fmap :: forall a b. (a -> b) -> NERAList a -> NERAList b
$c<$ :: forall a b. a -> NERAList b -> NERAList a
<$ :: forall a b. a -> NERAList b -> NERAList a
Functor, Functor NERAList
Foldable NERAList
(Functor NERAList, Foldable NERAList) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> NERAList a -> f (NERAList b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    NERAList (f a) -> f (NERAList a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> NERAList a -> m (NERAList b))
-> (forall (m :: * -> *) a.
    Monad m =>
    NERAList (m a) -> m (NERAList a))
-> Traversable NERAList
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => NERAList (m a) -> m (NERAList a)
forall (f :: * -> *) a.
Applicative f =>
NERAList (f a) -> f (NERAList a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NERAList a -> m (NERAList b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NERAList a -> f (NERAList b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NERAList a -> f (NERAList b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NERAList a -> f (NERAList b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
NERAList (f a) -> f (NERAList a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
NERAList (f a) -> f (NERAList a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NERAList a -> m (NERAList b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NERAList a -> m (NERAList b)
$csequence :: forall (m :: * -> *) a. Monad m => NERAList (m a) -> m (NERAList a)
sequence :: forall (m :: * -> *) a. Monad m => NERAList (m a) -> m (NERAList a)
I.Traversable)

-- | Non-empty random access list, underlying representation.
--
-- The structure doesn't need to be hidden, as polymorphic
-- recursion of 'Node's starting from 'Leaf' keeps the 'NERAList' values well-formed.
--
data NERAList' f a
    = Last (f a)
    | Cons0 (NERAList' (Node f) a)
    | Cons1 (f a) (NERAList' (Node f) a)
  deriving (NERAList' f a -> NERAList' f a -> Bool
(NERAList' f a -> NERAList' f a -> Bool)
-> (NERAList' f a -> NERAList' f a -> Bool) -> Eq (NERAList' f a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall (f :: * -> *) a.
Eq (f a) =>
NERAList' f a -> NERAList' f a -> Bool
$c== :: forall (f :: * -> *) a.
Eq (f a) =>
NERAList' f a -> NERAList' f a -> Bool
== :: NERAList' f a -> NERAList' f a -> Bool
$c/= :: forall (f :: * -> *) a.
Eq (f a) =>
NERAList' f a -> NERAList' f a -> Bool
/= :: NERAList' f a -> NERAList' f a -> Bool
Eq, Int -> NERAList' f a -> ShowS
[NERAList' f a] -> ShowS
NERAList' f a -> String
(Int -> NERAList' f a -> ShowS)
-> (NERAList' f a -> String)
-> ([NERAList' f a] -> ShowS)
-> Show (NERAList' f a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall (f :: * -> *) a. Show (f a) => Int -> NERAList' f a -> ShowS
forall (f :: * -> *) a. Show (f a) => [NERAList' f a] -> ShowS
forall (f :: * -> *) a. Show (f a) => NERAList' f a -> String
$cshowsPrec :: forall (f :: * -> *) a. Show (f a) => Int -> NERAList' f a -> ShowS
showsPrec :: Int -> NERAList' f a -> ShowS
$cshow :: forall (f :: * -> *) a. Show (f a) => NERAList' f a -> String
show :: NERAList' f a -> String
$cshowList :: forall (f :: * -> *) a. Show (f a) => [NERAList' f a] -> ShowS
showList :: [NERAList' f a] -> ShowS
Show, (forall a b. (a -> b) -> NERAList' f a -> NERAList' f b)
-> (forall a b. a -> NERAList' f b -> NERAList' f a)
-> Functor (NERAList' f)
forall a b. a -> NERAList' f b -> NERAList' f a
forall a b. (a -> b) -> NERAList' f a -> NERAList' f b
forall (f :: * -> *) a b.
Functor f =>
a -> NERAList' f b -> NERAList' f a
forall (f :: * -> *) a b.
Functor f =>
(a -> b) -> NERAList' f a -> NERAList' f b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall (f :: * -> *) a b.
Functor f =>
(a -> b) -> NERAList' f a -> NERAList' f b
fmap :: forall a b. (a -> b) -> NERAList' f a -> NERAList' f b
$c<$ :: forall (f :: * -> *) a b.
Functor f =>
a -> NERAList' f b -> NERAList' f a
<$ :: forall a b. a -> NERAList' f b -> NERAList' f a
Functor, (forall m. Monoid m => NERAList' f m -> m)
-> (forall m a. Monoid m => (a -> m) -> NERAList' f a -> m)
-> (forall m a. Monoid m => (a -> m) -> NERAList' f a -> m)
-> (forall a b. (a -> b -> b) -> b -> NERAList' f a -> b)
-> (forall a b. (a -> b -> b) -> b -> NERAList' f a -> b)
-> (forall b a. (b -> a -> b) -> b -> NERAList' f a -> b)
-> (forall b a. (b -> a -> b) -> b -> NERAList' f a -> b)
-> (forall a. (a -> a -> a) -> NERAList' f a -> a)
-> (forall a. (a -> a -> a) -> NERAList' f a -> a)
-> (forall a. NERAList' f a -> [a])
-> (forall a. NERAList' f a -> Bool)
-> (forall a. NERAList' f a -> Int)
-> (forall a. Eq a => a -> NERAList' f a -> Bool)
-> (forall a. Ord a => NERAList' f a -> a)
-> (forall a. Ord a => NERAList' f a -> a)
-> (forall a. Num a => NERAList' f a -> a)
-> (forall a. Num a => NERAList' f a -> a)
-> Foldable (NERAList' f)
forall a. Eq a => a -> NERAList' f a -> Bool
forall a. Num a => NERAList' f a -> a
forall a. Ord a => NERAList' f a -> a
forall m. Monoid m => NERAList' f m -> m
forall a. NERAList' f a -> Bool
forall a. NERAList' f a -> Int
forall a. NERAList' f a -> [a]
forall a. (a -> a -> a) -> NERAList' f a -> a
forall m a. Monoid m => (a -> m) -> NERAList' f a -> m
forall b a. (b -> a -> b) -> b -> NERAList' f a -> b
forall a b. (a -> b -> b) -> b -> NERAList' f a -> b
forall (f :: * -> *) a.
(Foldable f, Eq a) =>
a -> NERAList' f a -> Bool
forall (f :: * -> *) a. (Foldable f, Num a) => NERAList' f a -> a
forall (f :: * -> *) a. (Foldable f, Ord a) => NERAList' f a -> a
forall (f :: * -> *) m.
(Foldable f, Monoid m) =>
NERAList' f m -> m
forall (f :: * -> *) a. Foldable f => NERAList' f a -> Bool
forall (f :: * -> *) a. Foldable f => NERAList' f a -> Int
forall (f :: * -> *) a. Foldable f => NERAList' f a -> [a]
forall (f :: * -> *) a.
Foldable f =>
(a -> a -> a) -> NERAList' f a -> a
forall (f :: * -> *) m a.
(Foldable f, Monoid m) =>
(a -> m) -> NERAList' f a -> m
forall (f :: * -> *) b a.
Foldable f =>
(b -> a -> b) -> b -> NERAList' f a -> b
forall (f :: * -> *) a b.
Foldable f =>
(a -> b -> b) -> b -> NERAList' f a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall (f :: * -> *) m.
(Foldable f, Monoid m) =>
NERAList' f m -> m
fold :: forall m. Monoid m => NERAList' f m -> m
$cfoldMap :: forall (f :: * -> *) m a.
(Foldable f, Monoid m) =>
(a -> m) -> NERAList' f a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> NERAList' f a -> m
$cfoldMap' :: forall (f :: * -> *) m a.
(Foldable f, Monoid m) =>
(a -> m) -> NERAList' f a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> NERAList' f a -> m
$cfoldr :: forall (f :: * -> *) a b.
Foldable f =>
(a -> b -> b) -> b -> NERAList' f a -> b
foldr :: forall a b. (a -> b -> b) -> b -> NERAList' f a -> b
$cfoldr' :: forall (f :: * -> *) a b.
Foldable f =>
(a -> b -> b) -> b -> NERAList' f a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> NERAList' f a -> b
$cfoldl :: forall (f :: * -> *) b a.
Foldable f =>
(b -> a -> b) -> b -> NERAList' f a -> b
foldl :: forall b a. (b -> a -> b) -> b -> NERAList' f a -> b
$cfoldl' :: forall (f :: * -> *) b a.
Foldable f =>
(b -> a -> b) -> b -> NERAList' f a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> NERAList' f a -> b
$cfoldr1 :: forall (f :: * -> *) a.
Foldable f =>
(a -> a -> a) -> NERAList' f a -> a
foldr1 :: forall a. (a -> a -> a) -> NERAList' f a -> a
$cfoldl1 :: forall (f :: * -> *) a.
Foldable f =>
(a -> a -> a) -> NERAList' f a -> a
foldl1 :: forall a. (a -> a -> a) -> NERAList' f a -> a
$ctoList :: forall (f :: * -> *) a. Foldable f => NERAList' f a -> [a]
toList :: forall a. NERAList' f a -> [a]
$cnull :: forall (f :: * -> *) a. Foldable f => NERAList' f a -> Bool
null :: forall a. NERAList' f a -> Bool
$clength :: forall (f :: * -> *) a. Foldable f => NERAList' f a -> Int
length :: forall a. NERAList' f a -> Int
$celem :: forall (f :: * -> *) a.
(Foldable f, Eq a) =>
a -> NERAList' f a -> Bool
elem :: forall a. Eq a => a -> NERAList' f a -> Bool
$cmaximum :: forall (f :: * -> *) a. (Foldable f, Ord a) => NERAList' f a -> a
maximum :: forall a. Ord a => NERAList' f a -> a
$cminimum :: forall (f :: * -> *) a. (Foldable f, Ord a) => NERAList' f a -> a
minimum :: forall a. Ord a => NERAList' f a -> a
$csum :: forall (f :: * -> *) a. (Foldable f, Num a) => NERAList' f a -> a
sum :: forall a. Num a => NERAList' f a -> a
$cproduct :: forall (f :: * -> *) a. (Foldable f, Num a) => NERAList' f a -> a
product :: forall a. Num a => NERAList' f a -> a
I.Foldable, Functor (NERAList' f)
Foldable (NERAList' f)
(Functor (NERAList' f), Foldable (NERAList' f)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> NERAList' f a -> f (NERAList' f b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    NERAList' f (f a) -> f (NERAList' f a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> NERAList' f a -> m (NERAList' f b))
-> (forall (m :: * -> *) a.
    Monad m =>
    NERAList' f (m a) -> m (NERAList' f a))
-> Traversable (NERAList' f)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (f :: * -> *). Traversable f => Functor (NERAList' f)
forall (f :: * -> *). Traversable f => Foldable (NERAList' f)
forall (f :: * -> *) (m :: * -> *) a.
(Traversable f, Monad m) =>
NERAList' f (m a) -> m (NERAList' f a)
forall (f :: * -> *) (f :: * -> *) a.
(Traversable f, Applicative f) =>
NERAList' f (f a) -> f (NERAList' f a)
forall (f :: * -> *) (m :: * -> *) a b.
(Traversable f, Monad m) =>
(a -> m b) -> NERAList' f a -> m (NERAList' f b)
forall (f :: * -> *) (f :: * -> *) a b.
(Traversable f, Applicative f) =>
(a -> f b) -> NERAList' f a -> f (NERAList' f b)
forall (m :: * -> *) a.
Monad m =>
NERAList' f (m a) -> m (NERAList' f a)
forall (f :: * -> *) a.
Applicative f =>
NERAList' f (f a) -> f (NERAList' f a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NERAList' f a -> m (NERAList' f b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NERAList' f a -> f (NERAList' f b)
$ctraverse :: forall (f :: * -> *) (f :: * -> *) a b.
(Traversable f, Applicative f) =>
(a -> f b) -> NERAList' f a -> f (NERAList' f b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NERAList' f a -> f (NERAList' f b)
$csequenceA :: forall (f :: * -> *) (f :: * -> *) a.
(Traversable f, Applicative f) =>
NERAList' f (f a) -> f (NERAList' f a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
NERAList' f (f a) -> f (NERAList' f a)
$cmapM :: forall (f :: * -> *) (m :: * -> *) a b.
(Traversable f, Monad m) =>
(a -> m b) -> NERAList' f a -> m (NERAList' f b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NERAList' f a -> m (NERAList' f b)
$csequence :: forall (f :: * -> *) (m :: * -> *) a.
(Traversable f, Monad m) =>
NERAList' f (m a) -> m (NERAList' f a)
sequence :: forall (m :: * -> *) a.
Monad m =>
NERAList' f (m a) -> m (NERAList' f a)
I.Traversable)

-------------------------------------------------------------------------------
-- Instances
-------------------------------------------------------------------------------

instance (Ord a, I.Foldable f, Eq (f a)) => Ord (NERAList' f a) where
    compare :: NERAList' f a -> NERAList' f a -> Ordering
compare NERAList' f a
xs NERAList' f a
ys = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ((a -> [a] -> [a]) -> [a] -> NERAList' f a -> [a]
forall a b. (a -> b -> b) -> b -> NERAList' f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
I.foldr (:) [] NERAList' f a
xs) ((a -> [a] -> [a]) -> [a] -> NERAList' f a -> [a]
forall a b. (a -> b -> b) -> b -> NERAList' f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
I.foldr (:) [] NERAList' f a
ys)

-- |
--
-- >>> I.length $ fromNonEmpty $ 'x' :| ['a' .. 'z']
-- 27
--
instance I.Foldable NERAList where
    foldMap :: forall m a. Monoid m => (a -> m) -> NERAList a -> m
foldMap a -> m
f (NE NERAList' Leaf a
xs) = (a -> m) -> NERAList' Leaf a -> m
forall m a. Monoid m => (a -> m) -> NERAList' Leaf a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
I.foldMap a -> m
f NERAList' Leaf a
xs

    length :: forall a. NERAList a -> Int
length = NERAList a -> Int
forall a. NERAList a -> Int
length
    null :: forall a. NERAList a -> Bool
null   = NERAList a -> Bool
forall a. NERAList a -> Bool
null

#ifdef MIN_VERSION_semigroupoids
instance I.Foldable1 NERAList where
    foldMap1 :: forall m a. Semigroup m => (a -> m) -> NERAList a -> m
foldMap1 a -> m
f (NE NERAList' Leaf a
xs) = (a -> m) -> NERAList' Leaf a -> m
forall m a. Semigroup m => (a -> m) -> NERAList' Leaf a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
I.foldMap1 a -> m
f NERAList' Leaf a
xs

instance I.Foldable1 t => I.Foldable1 (NERAList' t) where
    foldMap1 :: forall m a. Semigroup m => (a -> m) -> NERAList' t a -> m
foldMap1 a -> m
f (Last  t a
t)   = (a -> m) -> t a -> m
forall m a. Semigroup m => (a -> m) -> t a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
I.foldMap1 a -> m
f t a
t
    foldMap1 a -> m
f (Cons0   NERAList' (Node t) a
r) = (a -> m) -> NERAList' (Node t) a -> m
forall m a. Semigroup m => (a -> m) -> NERAList' (Node t) a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
I.foldMap1 a -> m
f NERAList' (Node t) a
r
    foldMap1 a -> m
f (Cons1 t a
t NERAList' (Node t) a
r) = (a -> m) -> t a -> m
forall m a. Semigroup m => (a -> m) -> t a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
I.foldMap1 a -> m
f t a
t m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (a -> m) -> NERAList' (Node t) a -> m
forall m a. Semigroup m => (a -> m) -> NERAList' (Node t) a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
I.foldMap1 a -> m
f NERAList' (Node t) a
r

instance I.Traversable1 NERAList where
    traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NERAList a -> f (NERAList b)
traverse1 a -> f b
f (NE NERAList' Leaf a
xs) = NERAList' Leaf b -> NERAList b
forall a. NERAList' Leaf a -> NERAList a
NE (NERAList' Leaf b -> NERAList b)
-> f (NERAList' Leaf b) -> f (NERAList b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> NERAList' Leaf a -> f (NERAList' Leaf b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NERAList' Leaf a -> f (NERAList' Leaf b)
I.traverse1 a -> f b
f NERAList' Leaf a
xs where

instance I.Traversable1 t => I.Traversable1 (NERAList' t) where
    traverse1 :: forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NERAList' t a -> f (NERAList' t b)
traverse1 a -> f b
f (Last  t a
t)   = t b -> NERAList' t b
forall (f :: * -> *) a. f a -> NERAList' f a
Last (t b -> NERAList' t b) -> f (t b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b. Apply f => (a -> f b) -> t a -> f (t b)
I.traverse1 a -> f b
f t a
t
    traverse1 a -> f b
f (Cons0   NERAList' (Node t) a
r) = NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
I.traverse1 a -> f b
f NERAList' (Node t) a
r
    traverse1 a -> f b
f (Cons1 t a
t NERAList' (Node t) a
r) = t b -> NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1 (t b -> NERAList' (Node t) b -> NERAList' t b)
-> f (t b) -> f (NERAList' (Node t) b -> NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b. Apply f => (a -> f b) -> t a -> f (t b)
I.traverse1 a -> f b
f t a
t f (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> (a -> f b) -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable1 t, Apply f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
(a -> f b) -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
I.traverse1 a -> f b
f NERAList' (Node t) a
r
#endif

instance NFData a => NFData (NERAList a) where
    rnf :: NERAList a -> ()
rnf (NE NERAList' Leaf a
r) = NERAList' Leaf a -> ()
forall a. NFData a => a -> ()
rnf NERAList' Leaf a
r

instance NFData (t a) => NFData (NERAList' t a) where
    rnf :: NERAList' t a -> ()
rnf (Last t a
t)    = t a -> ()
forall a. NFData a => a -> ()
rnf t a
t
    rnf (Cons0   NERAList' (Node t) a
r) = NERAList' (Node t) a -> ()
forall a. NFData a => a -> ()
rnf NERAList' (Node t) a
r
    rnf (Cons1 t a
t NERAList' (Node t) a
r) = t a -> ()
forall a. NFData a => a -> ()
rnf t a
t () -> () -> ()
forall a b. a -> b -> b
`seq` NERAList' (Node t) a -> ()
forall a. NFData a => a -> ()
rnf NERAList' (Node t) a
r

instance Hashable a => Hashable (NERAList a) where
    hashWithSalt :: Int -> NERAList a -> Int
hashWithSalt Int
salt (NE NERAList' Leaf a
r) = Int -> NERAList' Leaf a -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt NERAList' Leaf a
r

instance Hashable (t a) => Hashable (NERAList' t a) where
    hashWithSalt :: Int -> NERAList' t a -> Int
hashWithSalt Int
salt (Last t a
t)    = Int
salt Int -> t a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` t a
t
    hashWithSalt Int
salt (Cons0   NERAList' (Node t) a
r) = Int
salt Int -> NERAList' (Node t) a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` NERAList' (Node t) a
r
    hashWithSalt Int
salt (Cons1 t a
t NERAList' (Node t) a
r) = Int
salt Int -> t a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` t a
t Int -> NERAList' (Node t) a -> Int
forall a. Hashable a => Int -> a -> Int
`hashWithSalt` NERAList' (Node t) a
r

-- |
--
-- >>> fromNonEmpty ('a' :| "bc") <> fromNonEmpty ('x' :| "yz")
-- fromNonEmpty ('a' :| "bcxyz")
--
instance Semigroup (NERAList a) where
    NE NERAList' Leaf a
xs <> :: NERAList a -> NERAList a -> NERAList a
<> NERAList a
ys = (a -> NERAList a -> NERAList a)
-> NERAList a -> NERAList' Leaf a -> NERAList a
forall a b. (a -> b -> b) -> b -> NERAList' Leaf a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
I.foldr a -> NERAList a -> NERAList a
forall a. a -> NERAList a -> NERAList a
cons NERAList a
ys NERAList' Leaf a
xs

-- TODO: Applicative, Monad

#ifdef MIN_VERSION_semigroupoids
-- Apply, Bind
#endif

-- | @since 0.2
instance WI.FunctorWithIndex Int NERAList where
    imap :: forall a b. (Int -> a -> b) -> NERAList a -> NERAList b
imap = (Int -> a -> b) -> NERAList a -> NERAList b
forall a b. (Int -> a -> b) -> NERAList a -> NERAList b
imap

-- | @since 0.2
instance WI.FoldableWithIndex Int NERAList where
    ifoldMap :: forall m a. Monoid m => (Int -> a -> m) -> NERAList a -> m
ifoldMap = (Int -> a -> m) -> NERAList a -> m
forall m a. Monoid m => (Int -> a -> m) -> NERAList a -> m
ifoldMap
    -- ifoldr   = ifoldr -- TODO, PR welcome!

-- | @since 0.2
instance WI.TraversableWithIndex Int NERAList where
    itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse = (Int -> a -> f b) -> NERAList a -> f (NERAList b)
forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse

-- | @since 0.2.1
instance Absurd a => Absurd (NERAList a) where
    absurd :: forall b. NERAList a -> b
absurd = a -> b
forall b. a -> b
forall a b. Absurd a => a -> b
absurd (a -> b) -> (NERAList a -> a) -> NERAList a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NERAList a -> a
forall a. NERAList a -> a
head

-------------------------------------------------------------------------------
-- Showing
-------------------------------------------------------------------------------

instance Show a => Show (NERAList a) where
    showsPrec :: Int -> NERAList a -> ShowS
showsPrec Int
d NERAList a
xs = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"fromNonEmpty " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> NonEmpty a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (NERAList a -> NonEmpty a
forall a. NERAList a -> NonEmpty a
toNonEmpty NERAList a
xs)

explicitShow :: Show a => NERAList a -> String
explicitShow :: forall a. Show a => NERAList a -> String
explicitShow NERAList a
xs = Int -> NERAList a -> ShowS
forall a. Show a => Int -> NERAList a -> ShowS
explicitShowsPrec Int
0 NERAList a
xs String
""

explicitShowsPrec :: Show a => Int -> NERAList a -> ShowS
explicitShowsPrec :: forall a. Show a => Int -> NERAList a -> ShowS
explicitShowsPrec Int
d (NE NERAList' Leaf a
xs) = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"NE " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> NERAList' Leaf a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 NERAList' Leaf a
xs

-------------------------------------------------------------------------------
-- Construction
-------------------------------------------------------------------------------

-- | Single element 'NERAList'.
singleton :: a -> NERAList a
singleton :: forall a. a -> NERAList a
singleton = NERAList' Leaf a -> NERAList a
forall a. NERAList' Leaf a -> NERAList a
NE (NERAList' Leaf a -> NERAList a)
-> (a -> NERAList' Leaf a) -> a -> NERAList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> NERAList' Leaf a
forall a. a -> NERAList' Leaf a
singleton'

singleton' :: a -> NERAList' Leaf a
singleton' :: forall a. a -> NERAList' Leaf a
singleton' = Leaf a -> NERAList' Leaf a
forall (f :: * -> *) a. f a -> NERAList' f a
Last (Leaf a -> NERAList' Leaf a)
-> (a -> Leaf a) -> a -> NERAList' Leaf a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Leaf a
forall a. a -> Leaf a
Lf

-- | 'cons' for non-empty rals.
cons :: a -> NERAList a -> NERAList a
cons :: forall a. a -> NERAList a -> NERAList a
cons a
x (NE NERAList' Leaf a
xs) = NERAList' Leaf a -> NERAList a
forall a. NERAList' Leaf a -> NERAList a
NE (Leaf a -> NERAList' Leaf a -> NERAList' Leaf a
forall (f :: * -> *) a. f a -> NERAList' f a -> NERAList' f a
consTree (a -> Leaf a
forall a. a -> Leaf a
Lf a
x) NERAList' Leaf a
xs)

consTree :: f a -> NERAList' f a -> NERAList' f a
consTree :: forall (f :: * -> *) a. f a -> NERAList' f a -> NERAList' f a
consTree f a
x (Last f a
t)    = NERAList' (Node f) a -> NERAList' f a
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (Node f a -> NERAList' (Node f) a
forall (f :: * -> *) a. f a -> NERAList' f a
Last (f a -> f a -> Node f a
forall (f :: * -> *) a. f a -> f a -> Node f a
Nd f a
x f a
t))
consTree f a
x (Cons0 NERAList' (Node f) a
r)   = f a -> NERAList' (Node f) a -> NERAList' f a
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1 f a
x NERAList' (Node f) a
r
consTree f a
x (Cons1 f a
t NERAList' (Node f) a
r) = NERAList' (Node f) a -> NERAList' f a
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (Node f a -> NERAList' (Node f) a -> NERAList' (Node f) a
forall (f :: * -> *) a. f a -> NERAList' f a -> NERAList' f a
consTree (f a -> f a -> Node f a
forall (f :: * -> *) a. f a -> f a -> Node f a
Nd f a
x f a
t) NERAList' (Node f) a
r)

-------------------------------------------------------------------------------
-- Conversions
-------------------------------------------------------------------------------

toNonEmpty :: NERAList a -> NonEmpty a
toNonEmpty :: forall a. NERAList a -> NonEmpty a
toNonEmpty = (a -> NonEmpty a -> NonEmpty a)
-> (a -> NonEmpty a) -> NERAList a -> NonEmpty a
forall a b. (a -> b -> b) -> (a -> b) -> NERAList a -> b
foldr1Map a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
NEList.cons (a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[])

toList :: NERAList a -> [a]
toList :: forall a. NERAList a -> [a]
toList = (a -> [a] -> [a]) -> [a] -> NERAList a -> [a]
forall a b. (a -> b -> b) -> b -> NERAList a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
I.foldr (:) []

-- |
--
-- >>> fromNonEmpty ('a' :| ['b'..'f'])
-- fromNonEmpty ('a' :| "bcdef")
--
-- >>> explicitShow (fromNonEmpty ('a' :| ['b'..'f']))
-- "NE (Cons0 (Cons1 (Nd (Lf 'a') (Lf 'b')) (Last (Nd (Nd (Lf 'c') (Lf 'd')) (Nd (Lf 'e') (Lf 'f'))))))"
--
fromNonEmpty :: NonEmpty a -> NERAList a
fromNonEmpty :: forall a. NonEmpty a -> NERAList a
fromNonEmpty (a
z :| [a]
zs) = a -> [a] -> NERAList a
forall {t}. t -> [t] -> NERAList t
go a
z [a]
zs where
    go :: t -> [t] -> NERAList t
go t
x []     = t -> NERAList t
forall a. a -> NERAList a
singleton t
x
    go t
x (t
y:[t]
ys) = t -> NERAList t -> NERAList t
forall a. a -> NERAList a -> NERAList a
cons t
x (t -> [t] -> NERAList t
go t
y [t]
ys)

-------------------------------------------------------------------------------
-- Indexing
-------------------------------------------------------------------------------

-- | List index.
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) ! 0
-- 'a'
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) ! 5
-- 'f'
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) ! 6
-- *** Exception: array index out of range: NERAList
-- ...
--
(!) :: NERAList a -> Int -> a
! :: forall a. NERAList a -> Int -> a
(!) (NE NERAList' Leaf a
xs) Int
i = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe (ArrayException -> a
forall a e. Exception e => e -> a
throw (ArrayException -> a) -> ArrayException -> a
forall a b. (a -> b) -> a -> b
$ String -> ArrayException
IndexOutOfBounds String
"NERAList") (NERAList' Leaf a -> Int -> Maybe a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> Int -> Maybe a
safeIndex' NERAList' Leaf a
xs Int
i)

-- | safe list index.
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) !? 0
-- Just 'a'
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) !? 5
-- Just 'f'
--
-- >>> fromNonEmpty ('a' :| ['b'..'f']) !? 6
-- Nothing
--
(!?) :: NERAList a -> Int -> Maybe a
NE NERAList' Leaf a
xs !? :: forall a. NERAList a -> Int -> Maybe a
!? Int
i = NERAList' Leaf a -> Int -> Maybe a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> Int -> Maybe a
safeIndex' NERAList' Leaf a
xs Int
i

safeIndex' :: Tr.IsTree f => NERAList' f a -> Int -> Maybe a
safeIndex' :: forall (f :: * -> *) a. IsTree f => NERAList' f a -> Int -> Maybe a
safeIndex' = Int -> NERAList' f a -> Int -> Maybe a
forall (g :: * -> *) a.
IsTree g =>
Int -> NERAList' g a -> Int -> Maybe a
go Int
1 where
    go :: Tr.IsTree g => Int -> NERAList' g a -> Int -> Maybe a
    go :: forall (g :: * -> *) a.
IsTree g =>
Int -> NERAList' g a -> Int -> Maybe a
go !Int
s (Last  g a
t)   Int
i = Int -> g a -> Int -> Maybe a
forall a. Int -> g a -> Int -> Maybe a
forall (t :: * -> *) a. IsTree t => Int -> t a -> Int -> Maybe a
Tr.safeIndex Int
s g a
t Int
i
    go  Int
s (Cons0   NERAList' (Node g) a
r) Int
i = Int -> NERAList' (Node g) a -> Int -> Maybe a
forall (g :: * -> *) a.
IsTree g =>
Int -> NERAList' g a -> Int -> Maybe a
go (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2) NERAList' (Node g) a
r Int
i
    go  Int
s (Cons1 g a
t NERAList' (Node g) a
r) Int
i
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s         = Int -> g a -> Int -> Maybe a
forall a. Int -> g a -> Int -> Maybe a
forall (t :: * -> *) a. IsTree t => Int -> t a -> Int -> Maybe a
Tr.safeIndex Int
s g a
t Int
i
        | Bool
otherwise     = Int -> NERAList' (Node g) a -> Int -> Maybe a
forall (g :: * -> *) a.
IsTree g =>
Int -> NERAList' g a -> Int -> Maybe a
go (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2) NERAList' (Node g) a
r (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s)

-- | First value, head of the list.
--
-- >>> head $ fromNonEmpty $ 'a' :| ['b'..'f']
-- 'a'
head :: NERAList a -> a
head :: forall a. NERAList a -> a
head (NE NERAList' Leaf a
x) = NERAList' Leaf a -> a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
head' NERAList' Leaf a
x

-- | Last value of the list
--
-- >>> last $ fromNonEmpty $  'a' :| ['b'..'f']
-- 'f'
--
last :: NERAList a -> a
last :: forall a. NERAList a -> a
last (NE NERAList' Leaf a
x) = NERAList' Leaf a -> a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
last' NERAList' Leaf a
x

head' :: Tr.IsTree f => NERAList' f a -> a
head' :: forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
head' (Last f a
t)    = f a -> a
forall a. f a -> a
forall (t :: * -> *) a. IsTree t => t a -> a
Tr.head f a
t
head' (Cons0 NERAList' (Node f) a
r)   = NERAList' (Node f) a -> a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
head' NERAList' (Node f) a
r
head' (Cons1 f a
t NERAList' (Node f) a
_) = f a -> a
forall a. f a -> a
forall (t :: * -> *) a. IsTree t => t a -> a
Tr.head f a
t

last' :: Tr.IsTree f => NERAList' f a -> a
last' :: forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
last' (Last f a
t)    = f a -> a
forall a. f a -> a
forall (t :: * -> *) a. IsTree t => t a -> a
Tr.last f a
t
last' (Cons0 NERAList' (Node f) a
r)   = NERAList' (Node f) a -> a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
last' NERAList' (Node f) a
r
last' (Cons1 f a
_ NERAList' (Node f) a
r) = NERAList' (Node f) a -> a
forall (f :: * -> *) a. IsTree f => NERAList' f a -> a
last' NERAList' (Node f) a
r

length :: NERAList a -> Int
length :: forall a. NERAList a -> Int
length (NE NERAList' Leaf a
xs) = Int -> Int -> NERAList' Leaf a -> Int
forall (n :: * -> *) a. Int -> Int -> NERAList' n a -> Int
go Int
0 Int
1 NERAList' Leaf a
xs where
    go :: Int -> Int -> NERAList' n a -> Int
    go :: forall (n :: * -> *) a. Int -> Int -> NERAList' n a -> Int
go !Int
acc Int
s (Last  n a
_)   = Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s
    go  Int
acc Int
s (Cons0   NERAList' (Node n) a
r) = Int -> Int -> NERAList' (Node n) a -> Int
forall (n :: * -> *) a. Int -> Int -> NERAList' n a -> Int
go Int
acc       (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node n) a
r
    go  Int
acc Int
s (Cons1 n a
_ NERAList' (Node n) a
r) = Int -> Int -> NERAList' (Node n) a -> Int
forall (n :: * -> *) a. Int -> Int -> NERAList' n a -> Int
go (Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node n) a
r

null :: NERAList a -> Bool
null :: forall a. NERAList a -> Bool
null NERAList a
_ = Bool
False

-------------------------------------------------------------------------------
-- Folds
-------------------------------------------------------------------------------

foldMap1 :: forall a s. Semigroup s => (a -> s) -> NERAList a -> s
foldMap1 :: forall a s. Semigroup s => (a -> s) -> NERAList a -> s
foldMap1 a -> s
f (NE NERAList' Leaf a
xs) = (Leaf a -> s) -> NERAList' Leaf a -> s
forall (t :: * -> *). (t a -> s) -> NERAList' t a -> s
go (\(Lf a
x) -> a -> s
f a
x) NERAList' Leaf a
xs where
    go :: (t a -> s) -> NERAList' t a -> s
    go :: forall (t :: * -> *). (t a -> s) -> NERAList' t a -> s
go t a -> s
g (Last  t a
t)   = t a -> s
g t a
t
    go t a -> s
g (Cons0   NERAList' (Node t) a
r) = (Node t a -> s) -> NERAList' (Node t) a -> s
forall (t :: * -> *). (t a -> s) -> NERAList' t a -> s
go (\(Nd t a
x t a
y) -> t a -> s
g t a
x s -> s -> s
forall a. Semigroup a => a -> a -> a
<> t a -> s
g t a
y) NERAList' (Node t) a
r
    go t a -> s
g (Cons1 t a
t NERAList' (Node t) a
r) = t a -> s
g t a
t s -> s -> s
forall a. Semigroup a => a -> a -> a
<> (Node t a -> s) -> NERAList' (Node t) a -> s
forall (t :: * -> *). (t a -> s) -> NERAList' t a -> s
go (\(Nd t a
x t a
y) -> t a -> s
g t a
x s -> s -> s
forall a. Semigroup a => a -> a -> a
<> t a -> s
g t a
y) NERAList' (Node t) a
r

foldr1Map :: (a -> b -> b) -> (a -> b) -> NERAList a -> b
foldr1Map :: forall a b. (a -> b -> b) -> (a -> b) -> NERAList a -> b
foldr1Map a -> b -> b
f a -> b
z (NE NERAList' Leaf a
xs) = (a -> b -> b) -> (a -> b) -> NERAList' Leaf a -> b
forall (f :: * -> *) a b.
IsTree f =>
(a -> b -> b) -> (a -> b) -> NERAList' f a -> b
foldr1Map' a -> b -> b
f a -> b
z NERAList' Leaf a
xs

foldr1Map' :: Tr.IsTree f => (a -> b -> b) -> (a -> b) -> NERAList' f a -> b
foldr1Map' :: forall (f :: * -> *) a b.
IsTree f =>
(a -> b -> b) -> (a -> b) -> NERAList' f a -> b
foldr1Map' a -> b -> b
f a -> b
z (Last  f a
t)   = (a -> b -> b) -> (a -> b) -> f a -> b
forall a b. (a -> b -> b) -> (a -> b) -> f a -> b
forall (t :: * -> *) a b.
IsTree t =>
(a -> b -> b) -> (a -> b) -> t a -> b
Tr.foldr1Map a -> b -> b
f a -> b
z f a
t
foldr1Map' a -> b -> b
f a -> b
z (Cons0  NERAList' (Node f) a
r)  = (a -> b -> b) -> (a -> b) -> NERAList' (Node f) a -> b
forall (f :: * -> *) a b.
IsTree f =>
(a -> b -> b) -> (a -> b) -> NERAList' f a -> b
foldr1Map' a -> b -> b
f a -> b
z NERAList' (Node f) a
r
foldr1Map' a -> b -> b
f a -> b
z (Cons1 f a
t NERAList' (Node f) a
r) = (a -> b -> b) -> b -> f a -> b
forall a b. (a -> b -> b) -> b -> f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
I.foldr a -> b -> b
f ((a -> b -> b) -> (a -> b) -> NERAList' (Node f) a -> b
forall (f :: * -> *) a b.
IsTree f =>
(a -> b -> b) -> (a -> b) -> NERAList' f a -> b
foldr1Map' a -> b -> b
f a -> b
z NERAList' (Node f) a
r) f a
t

ifoldMap :: Monoid m => (Int -> a -> m) -> NERAList a -> m
ifoldMap :: forall m a. Monoid m => (Int -> a -> m) -> NERAList a -> m
ifoldMap = (Int -> a -> m) -> NERAList a -> m
forall a s. Semigroup s => (Int -> a -> s) -> NERAList a -> s
ifoldMap1

-- |
--
-- >>> import Data.Semigroup (Min (..))
--
-- >>> ifoldMap1 (\_ x -> Min x) $ fromNonEmpty $ 5 :| [3,1,2,4]
-- Min {getMin = 1}
--
-- >>> ifoldMap1 (\i x -> Min (i + x)) $ fromNonEmpty $ 5 :| [3,1,2,4]
-- Min {getMin = 3}
--
ifoldMap1 :: forall a s. Semigroup s => (Int -> a -> s) -> NERAList a -> s
ifoldMap1 :: forall a s. Semigroup s => (Int -> a -> s) -> NERAList a -> s
ifoldMap1 Int -> a -> s
f (NE NERAList' Leaf a
xs) = Int -> Int -> NERAList' Leaf a -> s
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> s
go Int
0 Int
1 NERAList' Leaf a
xs where
    go :: Tr.IsTree t => Tr.Offset -> Tr.Size -> NERAList' t a -> s
    go :: forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> s
go Int
o Int
s (Last t a
t)    = Int -> Int -> (Int -> a -> s) -> t a -> s
forall s a.
Semigroup s =>
Int -> Int -> (Int -> a -> s) -> t a -> s
forall (t :: * -> *) s a.
(IsTree t, Semigroup s) =>
Int -> Int -> (Int -> a -> s) -> t a -> s
Tr.ifoldMap1 Int
o Int
s Int -> a -> s
f t a
t
    go Int
o Int
s (Cons0   NERAList' (Node t) a
r) = Int -> Int -> NERAList' (Node t) a -> s
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> s
go Int
o (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node t) a
r
    go Int
o Int
s (Cons1 t a
t NERAList' (Node t) a
r) = Int -> Int -> (Int -> a -> s) -> t a -> s
forall s a.
Semigroup s =>
Int -> Int -> (Int -> a -> s) -> t a -> s
forall (t :: * -> *) s a.
(IsTree t, Semigroup s) =>
Int -> Int -> (Int -> a -> s) -> t a -> s
Tr.ifoldMap1 Int
o Int
s Int -> a -> s
f t a
t s -> s -> s
forall a. Semigroup a => a -> a -> a
<> Int -> Int -> NERAList' (Node t) a -> s
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> s
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node t) a
r

ifoldr1Map :: forall a b. (Int -> a -> b -> b) -> (Int -> a -> b) -> NERAList a -> b
ifoldr1Map :: forall a b.
(Int -> a -> b -> b) -> (Int -> a -> b) -> NERAList a -> b
ifoldr1Map Int -> a -> b -> b
f Int -> a -> b
z (NE NERAList' Leaf a
xs) = Int -> Int -> NERAList' Leaf a -> b
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> b
go Int
0 Int
1 NERAList' Leaf a
xs where
    go :: Tr.IsTree t => Tr.Offset -> Tr.Size -> NERAList' t a -> b
    go :: forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> b
go Int
o Int
s (Last  t a
t)   = Int -> Int -> (Int -> a -> b -> b) -> (Int -> a -> b) -> t a -> b
forall a b.
Int -> Int -> (Int -> a -> b -> b) -> (Int -> a -> b) -> t a -> b
forall (t :: * -> *) a b.
IsTree t =>
Int -> Int -> (Int -> a -> b -> b) -> (Int -> a -> b) -> t a -> b
Tr.ifoldr1Map Int
o Int
s Int -> a -> b -> b
f Int -> a -> b
z t a
t
    go Int
o Int
s (Cons0   NERAList' (Node t) a
r) = Int -> Int -> NERAList' (Node t) a -> b
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> b
go Int
o (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2) NERAList' (Node t) a
r
    go Int
o Int
s (Cons1 t a
t NERAList' (Node t) a
r) = Int -> Int -> (Int -> a -> b -> b) -> b -> t a -> b
forall a b. Int -> Int -> (Int -> a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
IsTree t =>
Int -> Int -> (Int -> a -> b -> b) -> b -> t a -> b
Tr.ifoldr Int
o Int
s Int -> a -> b -> b
f (Int -> Int -> NERAList' (Node t) a -> b
forall (t :: * -> *). IsTree t => Int -> Int -> NERAList' t a -> b
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node t) a
r) t a
t

-------------------------------------------------------------------------------
-- Mapping
-------------------------------------------------------------------------------

-- |
-- >>> map toUpper (fromNonEmpty ('a' :| ['b'..'f']))
-- fromNonEmpty ('A' :| "BCDEF")
--
map :: (a -> b) -> NERAList a -> NERAList b
map :: forall a b. (a -> b) -> NERAList a -> NERAList b
map = (a -> b) -> NERAList a -> NERAList b
forall a b. (a -> b) -> NERAList a -> NERAList b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- |
--
-- >>> imap (,) (fromNonEmpty ('a' :| ['b'..'f']))
-- fromNonEmpty ((0,'a') :| [(1,'b'),(2,'c'),(3,'d'),(4,'e'),(5,'f')])
imap :: (Int -> a -> b) -> NERAList a -> NERAList b
imap :: forall a b. (Int -> a -> b) -> NERAList a -> NERAList b
imap Int -> a -> b
f NERAList a
xs = I (NERAList b) -> NERAList b
forall a. I a -> a
unI ((Int -> a -> I b) -> NERAList a -> I (NERAList b)
forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse (\Int
i a
x -> b -> I b
forall a. a -> I a
I (Int -> a -> b
f Int
i a
x)) NERAList a
xs)

itraverse :: forall f a b. Applicative f => (Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse Int -> a -> f b
f (NE NERAList' Leaf a
xs) = NERAList' Leaf b -> NERAList b
forall a. NERAList' Leaf a -> NERAList a
NE (NERAList' Leaf b -> NERAList b)
-> f (NERAList' Leaf b) -> f (NERAList b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> NERAList' Leaf a -> f (NERAList' Leaf b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go Int
0 Int
1 NERAList' Leaf a
xs where
    go :: Tr.IsTree t => Tr.Offset -> Tr.Size -> NERAList' t a -> f (NERAList' t b)
    go :: forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go !Int
o !Int
s (Last  t a
t)   = t b -> NERAList' t b
forall (f :: * -> *) a. f a -> NERAList' f a
Last (t b -> NERAList' t b) -> f (t b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(IsTree t, Applicative f) =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
Tr.itraverse Int
o Int
s Int -> a -> f b
f t a
t
    go  Int
o  Int
s (Cons0   NERAList' (Node t) a
r) = NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go Int
o (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) NERAList' (Node t) a
r
    go  Int
o  Int
s (Cons1 t a
t NERAList' (Node t) a
r) = t b -> NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1
      (t b -> NERAList' (Node t) b -> NERAList' t b)
-> f (t b) -> f (NERAList' (Node t) b -> NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(IsTree t, Applicative f) =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
Tr.itraverse Int
o Int
s Int -> a -> f b
f t a
t
      f (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Int -> Int -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) NERAList' (Node t) a
r

#ifdef MIN_VERSION_semigroupoids
itraverse1 :: forall f a b. Apply f => (Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse1 :: forall (f :: * -> *) a b.
Apply f =>
(Int -> a -> f b) -> NERAList a -> f (NERAList b)
itraverse1 Int -> a -> f b
f (NE NERAList' Leaf a
xs) = NERAList' Leaf b -> NERAList b
forall a. NERAList' Leaf a -> NERAList a
NE (NERAList' Leaf b -> NERAList b)
-> f (NERAList' Leaf b) -> f (NERAList b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> NERAList' Leaf a -> f (NERAList' Leaf b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go Int
0 Int
1 NERAList' Leaf a
xs where
    go :: Tr.IsTree t => Tr.Offset -> Tr.Size -> NERAList' t a -> f (NERAList' t b)
    go :: forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go !Int
o !Int
s (Last  t a
t)   = t b -> NERAList' t b
forall (f :: * -> *) a. f a -> NERAList' f a
Last (t b -> NERAList' t b) -> f (t b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(IsTree t, Apply f) =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
Tr.itraverse1 Int
o Int
s Int -> a -> f b
f t a
t
    go  Int
o  Int
s (Cons0   NERAList' (Node t) a
r) = NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go Int
o (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) NERAList' (Node t) a
r
    go  Int
o  Int
s (Cons1 t a
t NERAList' (Node t) a
r) = t b -> NERAList' (Node t) b -> NERAList' t b
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1
      (t b -> NERAList' (Node t) b -> NERAList' t b)
-> f (t b) -> f (NERAList' (Node t) b -> NERAList' t b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(IsTree t, Apply f) =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Apply f =>
Int -> Int -> (Int -> a -> f b) -> t a -> f (t b)
Tr.itraverse1 Int
o Int
s Int -> a -> f b
f t a
t
      f (NERAList' (Node t) b -> NERAList' t b)
-> f (NERAList' (Node t) b) -> f (NERAList' t b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> Int -> Int -> NERAList' (Node t) a -> f (NERAList' (Node t) b)
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> f (NERAList' t b)
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) NERAList' (Node t) a
r
#endif

-- | Adjust a value in the list.
--
-- >>> adjust 3 toUpper $ fromNonEmpty $ 'a' :| "bcdef"
-- fromNonEmpty ('a' :| "bcDef")
--
-- If index is out of bounds, the list is returned unmodified.
--
-- >>> adjust 10 toUpper $ fromNonEmpty $ 'a' :| "bcdef"
-- fromNonEmpty ('a' :| "bcdef")
--
-- >>> adjust (-1) toUpper $ fromNonEmpty $ 'a' :| "bcdef"
-- fromNonEmpty ('a' :| "bcdef")
--
adjust :: forall a. Int -> (a -> a) -> NERAList a -> NERAList a
adjust :: forall a. Int -> (a -> a) -> NERAList a -> NERAList a
adjust Int
i a -> a
_ NERAList a
xs | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = NERAList a
xs
adjust Int
i a -> a
f (NE NERAList' Leaf a
xs) = NERAList' Leaf a -> NERAList a
forall a. NERAList' Leaf a -> NERAList a
NE (Int -> Int -> NERAList' Leaf a -> NERAList' Leaf a
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> NERAList' t a
go Int
0 Int
1 NERAList' Leaf a
xs) where
    go :: Tr.IsTree t => Tr.Offset -> Tr.Size -> NERAList' t a -> NERAList' t a
    go :: forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> NERAList' t a
go !Int
o !Int
s (Last  t a
t)   = t a -> NERAList' t a
forall (f :: * -> *) a. f a -> NERAList' f a
Last (Int -> Int -> (a -> a) -> t a -> t a
forall a. Int -> Int -> (a -> a) -> t a -> t a
forall (t :: * -> *) a.
IsTree t =>
Int -> Int -> (a -> a) -> t a -> t a
Tr.adjust Int
s (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
o) a -> a
f t a
t)
    go  Int
o  Int
s (Cons0   NERAList' (Node t) a
r) = NERAList' (Node t) a -> NERAList' t a
forall (f :: * -> *) a. NERAList' (Node f) a -> NERAList' f a
Cons0 (Int -> Int -> NERAList' (Node t) a -> NERAList' (Node t) a
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> NERAList' t a
go Int
o (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node t) a
r)
    go  Int
o  Int
s (Cons1 t a
t NERAList' (Node t) a
r)
        | Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
o Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
s = t a -> NERAList' (Node t) a -> NERAList' t a
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1 (Int -> Int -> (a -> a) -> t a -> t a
forall a. Int -> Int -> (a -> a) -> t a -> t a
forall (t :: * -> *) a.
IsTree t =>
Int -> Int -> (a -> a) -> t a -> t a
Tr.adjust Int
s (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
o) a -> a
f t a
t) NERAList' (Node t) a
r
        | Bool
otherwise = t a -> NERAList' (Node t) a -> NERAList' t a
forall (f :: * -> *) a.
f a -> NERAList' (Node f) a -> NERAList' f a
Cons1 t a
t (Int -> Int -> NERAList' (Node t) a -> NERAList' (Node t) a
forall (t :: * -> *).
IsTree t =>
Int -> Int -> NERAList' t a -> NERAList' t a
go (Int
o Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
s) NERAList' (Node t) a
r)

-------------------------------------------------------------------------------
-- QuickCheck
-------------------------------------------------------------------------------

instance QC.Arbitrary1 NERAList where
    liftArbitrary :: forall a. Gen a -> Gen (NERAList a)
liftArbitrary Gen a
arb = do
        a
x  <- Gen a
arb
        [a]
xs <- Gen a -> Gen [a]
forall a. Gen a -> Gen [a]
forall (f :: * -> *) a. Arbitrary1 f => Gen a -> Gen (f a)
QC.liftArbitrary Gen a
arb
        NERAList a -> Gen (NERAList a)
forall a. a -> Gen a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (NonEmpty a -> NERAList a
forall a. NonEmpty a -> NERAList a
fromNonEmpty (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs))

    liftShrink :: forall a. (a -> [a]) -> NERAList a -> [NERAList a]
liftShrink a -> [a]
shr
        = ((a, [a]) -> NERAList a) -> [(a, [a])] -> [NERAList a]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(a
x,[a]
xs) -> NonEmpty a -> NERAList a
forall a. NonEmpty a -> NERAList a
fromNonEmpty (a
xa -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[a]
xs))
        ([(a, [a])] -> [NERAList a])
-> (NERAList a -> [(a, [a])]) -> NERAList a -> [NERAList a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> [a]) -> ([a] -> [[a]]) -> (a, [a]) -> [(a, [a])]
forall a b. (a -> [a]) -> (b -> [b]) -> (a, b) -> [(a, b)]
forall (f :: * -> * -> *) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
QC.liftShrink2 a -> [a]
shr ((a -> [a]) -> [a] -> [[a]]
forall a. (a -> [a]) -> [a] -> [[a]]
forall (f :: * -> *) a. Arbitrary1 f => (a -> [a]) -> f a -> [f a]
QC.liftShrink a -> [a]
shr)
        ((a, [a]) -> [(a, [a])])
-> (NERAList a -> (a, [a])) -> NERAList a -> [(a, [a])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (\(a
x:|[a]
xs) -> (a
x,[a]
xs)) (NonEmpty a -> (a, [a]))
-> (NERAList a -> NonEmpty a) -> NERAList a -> (a, [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NERAList a -> NonEmpty a
forall a. NERAList a -> NonEmpty a
toNonEmpty

instance QC.Arbitrary a => QC.Arbitrary (NERAList a) where
    arbitrary :: Gen (NERAList a)
arbitrary = Gen (NERAList a)
forall (f :: * -> *) a. (Arbitrary1 f, Arbitrary a) => Gen (f a)
QC.arbitrary1
    shrink :: NERAList a -> [NERAList a]
shrink    = NERAList a -> [NERAList a]
forall (f :: * -> *) a. (Arbitrary1 f, Arbitrary a) => f a -> [f a]
QC.shrink1

instance QC.CoArbitrary a => QC.CoArbitrary (NERAList a) where
    coarbitrary :: forall b. NERAList a -> Gen b -> Gen b
coarbitrary NERAList a
xs = (a, [a]) -> Gen b -> Gen b
forall b. (a, [a]) -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
QC.coarbitrary (a
y, [a]
ys) where
        (a
y:|[a]
ys) = NERAList a -> NonEmpty a
forall a. NERAList a -> NonEmpty a
toNonEmpty NERAList a
xs

instance QC.Function a => QC.Function (NERAList a) where
    function :: forall b. (NERAList a -> b) -> NERAList a :-> b
function = (NERAList a -> (a, [a]))
-> ((a, [a]) -> NERAList a)
-> (NERAList a -> b)
-> NERAList a :-> b
forall b a c.
Function b =>
(a -> b) -> (b -> a) -> (a -> c) -> a :-> c
QC.functionMap (NonEmpty a -> (a, [a])
forall {a}. NonEmpty a -> (a, [a])
fwd (NonEmpty a -> (a, [a]))
-> (NERAList a -> NonEmpty a) -> NERAList a -> (a, [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NERAList a -> NonEmpty a
forall a. NERAList a -> NonEmpty a
toNonEmpty) (NonEmpty a -> NERAList a
forall a. NonEmpty a -> NERAList a
fromNonEmpty (NonEmpty a -> NERAList a)
-> ((a, [a]) -> NonEmpty a) -> (a, [a]) -> NERAList a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, [a]) -> NonEmpty a
forall {a}. (a, [a]) -> NonEmpty a
bwd) where
        fwd :: NonEmpty a -> (a, [a])
fwd (a
x :| [a]
xs) = (a
x, [a]
xs)
        bwd :: (a, [a]) -> NonEmpty a
bwd (a
x, [a]
xs) = a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs

-------------------------------------------------------------------------------
-- Utilities
-------------------------------------------------------------------------------

newtype I a = I a
unI :: I a -> a
unI :: forall a. I a -> a
unI (I a
a) = a
a

instance Functor I where
    fmap :: forall a b. (a -> b) -> I a -> I b
fmap a -> b
f (I a
x) = b -> I b
forall a. a -> I a
I (a -> b
f a
x)

instance Applicative I where
    pure :: forall a. a -> I a
pure        = a -> I a
forall a. a -> I a
I
    I a -> b
f <*> :: forall a b. I (a -> b) -> I a -> I b
<*> I a
x = b -> I b
forall a. a -> I a
I (a -> b
f a
x)
    I a
_ *> :: forall a b. I a -> I b -> I b
*> I b
x      = I b
x
    I a
x <* :: forall a b. I a -> I b -> I a
<* I b
_      = I a
x
    liftA2 :: forall a b c. (a -> b -> c) -> I a -> I b -> I c
liftA2 a -> b -> c
f (I a
x) (I b
y) = c -> I c
forall a. a -> I a
I (a -> b -> c
f a
x b
y)