-- Functional patterns yielding non-linear constructor terms:
import Control.Search.SetFunctions
import Data.List (nub)

idpair x = (x,x)

f (idpair x) = 0

--> Semantics: f (x,x) = 0
--> meaning: f (x,y) | x =:= y = 0

--> f (failed,failed)  should fail!
--> Consequence: check whether the functional pattern evaluates to terms
--  with multiple variable occurrences!

zero x = 0

pair x y = (x,y)

g (pair (zero x) x) = 0

--> Semantics: g (0,x) = 0

-- Implementation of non-strict equality: check multiplicity of pattern
-- variables

-- Therefore: (=:<=) :: Data a => a -> a -> Bool


-----------------------------------------------------------------------------

-- Applications of functional patterns:

-- Definition of a permutation:
perm :: Data a => [a] -> [a]
perm []                = []
perm (xs ++ [x] ++ ys) = x : perm (xs ++ ys)

-- Non-ascending lists:
nonAscending :: [Int] -> Bool
nonAscending (_ ++ x : y : _) | x > y = True

sort :: [Int] -> [Int]
sort xs | isEmpty (set1 nonAscending p) = p
 where p = perm xs

-------------------------------------------------------------------------

-- Task: Given some list of data, compute the length of the initial list
--       until the first repeated element

lengthUpToRepeat :: (Data a, Eq a) => [a] -> Int
-- lengthUpToRepeat [1,2,4,5,42,99,2,3,1,5] --> 7
lengthUpToRepeat (p ++ r : _)
  | r `elem` p && nub p == p
  = length p + 1