{-# OPTIONS_GHC -Wall -fno-warn-tabs #-}

module Data.List.Infinite (
	-- * Definition
	Infinite(..), NonEmpty(..),
	-- * Basic functions
	append, uncons, concat,
	-- * List transformations
	intersperse, intercalate, subsequences,
	-- * Reducing lists (folds)
	foldr,
	-- * Scans
	scanl, scanl',
	-- * Infinite lists
	iterate, iterate', repeat, cycle, unfoldr,
	-- * Extracting sublits
	take, drop, splitAt, span, group, groupBy, inits,
	-- * Predicates
	isPrefixOf,
	-- * Searching
	partition,
	-- * Indexing lists
	index,
	-- * Zipping and unzipping lists
	zipWith, unzip,
	-- * "Set" operations
	delete, (\\),
	-- * Ordered lists
	insert, insertBy
	) where

import Prelude hiding (
	cycle, (++), concat, scanl, iterate, repeat,
	span, take, drop, splitAt, zipWith, unzip )

import Control.Arrow (first, second, (***))

import Data.List.NonEmpty (NonEmpty(..))

-- DEFINITION

infixr 5 :~

data Infinite a = a :~ Infinite a

instance Functor Infinite where a -> b
f fmap :: forall a b. (a -> b) -> Infinite a -> Infinite b
`fmap` (a
x :~ Infinite a
xs) = a -> b
f a
x forall a. a -> Infinite a -> Infinite a
:~ (a -> b
f forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Infinite a
xs)

instance Applicative Infinite where
	pure :: forall a. a -> Infinite a
pure a
x = a
x forall a. a -> Infinite a -> Infinite a
:~ forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x
	(a -> b
f :~ Infinite (a -> b)
fs) <*> :: forall a b. Infinite (a -> b) -> Infinite a -> Infinite b
<*> (a
x :~ Infinite a
xs) = a -> b
f a
x forall a. a -> Infinite a -> Infinite a
:~ (Infinite (a -> b)
fs forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Infinite a
xs)

instance Foldable Infinite where
	foldr :: forall a b. (a -> b -> b) -> b -> Infinite a -> b
foldr a -> b -> b
op b
v (a
x :~ Infinite a
xs) = a
x a -> b -> b
`op` forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
op b
v Infinite a
xs

-- BASIC FUNCTIONS

append :: [a] -> Infinite a -> Infinite a
[] append :: forall a. [a] -> Infinite a -> Infinite a
`append` Infinite a
ys = Infinite a
ys
(a
x : [a]
xs) `append` Infinite a
ys = a
x forall a. a -> Infinite a -> Infinite a
:~ ([a]
xs forall a. [a] -> Infinite a -> Infinite a
`append` Infinite a
ys)

uncons :: Infinite a -> (a, Infinite a)
uncons :: forall a. Infinite a -> (a, Infinite a)
uncons (a
x :~ Infinite a
xs) = (a
x, Infinite a
xs)

concat :: Infinite [a] -> Infinite a
concat :: forall a. Infinite [a] -> Infinite a
concat ([] :~ Infinite [a]
xss) = forall a. Infinite [a] -> Infinite a
concat Infinite [a]
xss
concat ((a
x : [a]
xs) :~ Infinite [a]
xss) = a
x forall a. a -> Infinite a -> Infinite a
:~ forall a. Infinite [a] -> Infinite a
concat ([a]
xs forall a. a -> Infinite a -> Infinite a
:~ Infinite [a]
xss)

-- LIST TRANSFORMATIONS

intersperse :: a -> Infinite a -> Infinite a
intersperse :: forall a. a -> Infinite a -> Infinite a
intersperse a
x (a
y :~ Infinite a
ys) = a
y forall a. a -> Infinite a -> Infinite a
:~ a
x forall a. a -> Infinite a -> Infinite a
:~ forall a. a -> Infinite a -> Infinite a
intersperse a
x Infinite a
ys

intercalate :: [a] -> Infinite [a] -> Infinite a
intercalate :: forall a. [a] -> Infinite [a] -> Infinite a
intercalate [a]
xs ([a]
ys :~ Infinite [a]
yss) = [a]
ys forall a. [a] -> Infinite a -> Infinite a
`append` ([a]
xs forall a. [a] -> Infinite a -> Infinite a
`append` forall a. [a] -> Infinite [a] -> Infinite a
intercalate [a]
xs Infinite [a]
yss)

subsequences, nonEmptySubsequences :: Infinite a -> Infinite [a]
subsequences :: forall a. Infinite a -> Infinite [a]
subsequences Infinite a
xs = [] forall a. a -> Infinite a -> Infinite a
:~ forall a. Infinite a -> Infinite [a]
nonEmptySubsequences Infinite a
xs

nonEmptySubsequences :: forall a. Infinite a -> Infinite [a]
nonEmptySubsequences (a
x :~ Infinite a
xs) =
	[a
x] forall a. a -> Infinite a -> Infinite a
:~ forall a. Infinite [a] -> Infinite a
concat ((\[a]
ys -> [[a]
ys, a
x forall a. a -> [a] -> [a]
: [a]
ys]) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Infinite a -> Infinite [a]
nonEmptySubsequences Infinite a
xs)

-- REDUCING LISTS (FOLDS)

-- SCANS

scanl, scanl' :: (b -> a -> b) -> b -> Infinite a -> Infinite b
scanl :: forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
scanl b -> a -> b
op b
z (a
x :~ Infinite a
xs) = b
z forall a. a -> Infinite a -> Infinite a
:~ forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
scanl b -> a -> b
op (b
z b -> a -> b
`op` a
x) Infinite a
xs
scanl' :: forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
scanl' b -> a -> b
op b
z (a
x :~ Infinite a
xs) = b
z seq :: forall a b. a -> b -> b
`seq` b
z forall a. a -> Infinite a -> Infinite a
:~ forall b a. (b -> a -> b) -> b -> Infinite a -> Infinite b
scanl' b -> a -> b
op (b
z b -> a -> b
`op` a
x) Infinite a
xs

-- INFINITE LISTS

iterate, iterate' :: (a -> a) -> a -> Infinite a
iterate :: forall a. (a -> a) -> a -> Infinite a
iterate a -> a
f a
x = a
x forall a. a -> Infinite a -> Infinite a
:~ forall a. (a -> a) -> a -> Infinite a
iterate a -> a
f (a -> a
f a
x)
iterate' :: forall a. (a -> a) -> a -> Infinite a
iterate' a -> a
f a
x = a
x seq :: forall a b. a -> b -> b
`seq` a
x forall a. a -> Infinite a -> Infinite a
:~ forall a. (a -> a) -> a -> Infinite a
iterate a -> a
f (a -> a
f a
x)

repeat :: a -> Infinite a
repeat :: forall a. a -> Infinite a
repeat a
x = a
x forall a. a -> Infinite a -> Infinite a
:~ forall a. a -> Infinite a
repeat a
x

cycle :: NonEmpty a -> Infinite a
cycle :: forall a. NonEmpty a -> Infinite a
cycle NonEmpty a
xs = NonEmpty a -> Infinite a
ccl NonEmpty a
xs where
	ccl :: NonEmpty a -> Infinite a
ccl (a
y :| [a]
ys) = a
y forall a. a -> Infinite a -> Infinite a
:~ case [a]
ys of
		[] -> forall a. NonEmpty a -> Infinite a
cycle NonEmpty a
xs
		(a
z : [a]
zs) -> NonEmpty a -> Infinite a
ccl (a
z forall a. a -> [a] -> NonEmpty a
:| [a]
zs)

unfoldr :: (b -> (a, b)) -> b -> Infinite a
unfoldr :: forall b a. (b -> (a, b)) -> b -> Infinite a
unfoldr b -> (a, b)
f b
s = a
x forall a. a -> Infinite a -> Infinite a
:~ forall b a. (b -> (a, b)) -> b -> Infinite a
unfoldr b -> (a, b)
f b
s' where (a
x, b
s') = b -> (a, b)
f b
s

-- SUBLISTS

take :: Integral i => i -> Infinite a -> [a]
take :: forall i a. Integral i => i -> Infinite a -> [a]
take i
n = forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a. Integral i => i -> Infinite a -> ([a], Infinite a)
splitAt i
n

drop :: Integral i => i -> Infinite a -> Infinite a
drop :: forall i a. Integral i => i -> Infinite a -> Infinite a
drop i
n = forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a. Integral i => i -> Infinite a -> ([a], Infinite a)
splitAt i
n

splitAt :: Integral i => i -> Infinite a -> ([a], Infinite a)
splitAt :: forall i a. Integral i => i -> Infinite a -> ([a], Infinite a)
splitAt i
n Infinite a
xs | i
n forall a. Ord a => a -> a -> Bool
< i
1 = ([], Infinite a
xs)
splitAt i
n (a
x :~ Infinite a
xs) = (a
x forall a. a -> [a] -> [a]
:) forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
`first` forall i a. Integral i => i -> Infinite a -> ([a], Infinite a)
splitAt (i
n forall a. Num a => a -> a -> a
- i
1) Infinite a
xs

span :: (a -> Bool) -> Infinite a -> ([a], Infinite a)
span :: forall a. (a -> Bool) -> Infinite a -> ([a], Infinite a)
span a -> Bool
p xa :: Infinite a
xa@(a
x :~ Infinite a
xs)
	| a -> Bool
p a
x = (a
x forall a. a -> [a] -> [a]
:) forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
`first` forall a. (a -> Bool) -> Infinite a -> ([a], Infinite a)
span a -> Bool
p Infinite a
xs
	| Bool
otherwise = ([], Infinite a
xa)

group :: Eq a => Infinite a -> Infinite [a]
group :: forall a. Eq a => Infinite a -> Infinite [a]
group = forall a. (a -> a -> Bool) -> Infinite a -> Infinite [a]
groupBy forall a. Eq a => a -> a -> Bool
(==)

groupBy :: (a -> a -> Bool) -> Infinite a -> Infinite [a]
groupBy :: forall a. (a -> a -> Bool) -> Infinite a -> Infinite [a]
groupBy a -> a -> Bool
eq (a
x :~ Infinite a
xs) = (a
x forall a. a -> [a] -> [a]
: [a]
ys) forall a. a -> Infinite a -> Infinite a
:~ forall a. (a -> a -> Bool) -> Infinite a -> Infinite [a]
groupBy a -> a -> Bool
eq Infinite a
zs
	where ([a]
ys, Infinite a
zs) = forall a. (a -> Bool) -> Infinite a -> ([a], Infinite a)
span (a
x a -> a -> Bool
`eq`) Infinite a
xs

inits :: Infinite a -> Infinite [a]
inits :: forall a. Infinite a -> Infinite [a]
inits (a
x :~ Infinite a
xs) = [] forall a. a -> Infinite a -> Infinite a
:~ ((a
x forall a. a -> [a] -> [a]
:) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Infinite a -> Infinite [a]
inits Infinite a
xs)

-- PREDICATES

isPrefixOf :: Eq a => [a] -> Infinite a -> Bool
isPrefixOf :: forall a. Eq a => [a] -> Infinite a -> Bool
isPrefixOf [] Infinite a
_ = Bool
True
isPrefixOf (a
x : [a]
xs) (a
y :~ Infinite a
ys) = a
x forall a. Eq a => a -> a -> Bool
== a
y Bool -> Bool -> Bool
&& forall a. Eq a => [a] -> Infinite a -> Bool
isPrefixOf [a]
xs Infinite a
ys

-- SEARCHING LISTS

partition :: (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
partition :: forall a. (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
partition a -> Bool
p (a
x :~ Infinite a
xs)
	| a -> Bool
p a
x = (a
x forall a. a -> Infinite a -> Infinite a
:~) forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
`first` forall a. (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
partition a -> Bool
p Infinite a
xs
	| Bool
otherwise = (a
x forall a. a -> Infinite a -> Infinite a
:~) forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
`second` forall a. (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
partition a -> Bool
p Infinite a
xs

-- INDEXING LISTS

infixl 9 `index`

index :: Integral i => Infinite a -> i -> a
Infinite a
_ index :: forall i a. Integral i => Infinite a -> i -> a
`index` i
n | i
n forall a. Ord a => a -> a -> Bool
< i
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"negative index"
(a
x :~ Infinite a
_) `index` i
0 = a
x
(a
_ :~ Infinite a
xs) `index` i
n = Infinite a
xs forall i a. Integral i => Infinite a -> i -> a
`index` (i
n forall a. Num a => a -> a -> a
- i
1)

-- ZIPPING AND UNZIPPING LISTS

zipWith :: (a -> b -> c) -> Infinite a -> Infinite b -> Infinite c
zipWith :: forall a b c.
(a -> b -> c) -> Infinite a -> Infinite b -> Infinite c
zipWith a -> b -> c
op (a
x :~ Infinite a
xs) (b
y :~ Infinite b
ys) = (a
x a -> b -> c
`op` b
y) forall a. a -> Infinite a -> Infinite a
:~ forall a b c.
(a -> b -> c) -> Infinite a -> Infinite b -> Infinite c
zipWith a -> b -> c
op Infinite a
xs Infinite b
ys

unzip :: Infinite (a, b) -> (Infinite a, Infinite b)
unzip :: forall a b. Infinite (a, b) -> (Infinite a, Infinite b)
unzip ((a
x, b
y) :~ Infinite (a, b)
xys) = (a
x forall a. a -> Infinite a -> Infinite a
:~) forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** (b
y forall a. a -> Infinite a -> Infinite a
:~) forall a b. (a -> b) -> a -> b
$ forall a b. Infinite (a, b) -> (Infinite a, Infinite b)
unzip Infinite (a, b)
xys

-- SET OPERATIONS

delete :: Eq a => a -> Infinite a -> Infinite a
delete :: forall a. Eq a => a -> Infinite a -> Infinite a
delete a
x (a
y :~ Infinite a
ys)
	| a
x forall a. Eq a => a -> a -> Bool
== a
y = Infinite a
ys
	| Bool
otherwise = a
y forall a. a -> Infinite a -> Infinite a
:~ forall a. Eq a => a -> Infinite a -> Infinite a
delete a
x Infinite a
ys

(\\) :: Eq a => Infinite a -> [a] -> Infinite a
\\ :: forall a. Eq a => Infinite a -> [a] -> Infinite a
(\\) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl forall a b. (a -> b) -> a -> b
$ forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. Eq a => a -> Infinite a -> Infinite a
delete

-- ORDERED LISTS

insert :: Ord a => a -> Infinite a -> Infinite a
insert :: forall a. Ord a => a -> Infinite a -> Infinite a
insert = forall a. (a -> a -> Ordering) -> a -> Infinite a -> Infinite a
insertBy forall a. Ord a => a -> a -> Ordering
compare

insertBy :: (a -> a -> Ordering) -> a -> Infinite a -> Infinite a
insertBy :: forall a. (a -> a -> Ordering) -> a -> Infinite a -> Infinite a
insertBy a -> a -> Ordering
cmp a
x ya :: Infinite a
ya@(a
y :~ Infinite a
ys) = case a -> a -> Ordering
cmp a
x a
y of
	Ordering
GT -> a
y forall a. a -> Infinite a -> Infinite a
:~ forall a. (a -> a -> Ordering) -> a -> Infinite a -> Infinite a
insertBy a -> a -> Ordering
cmp a
x Infinite a
ys
	Ordering
_ -> a
x forall a. a -> Infinite a -> Infinite a
:~ Infinite a
ya