foldr - insert - paramorphism

foldr-insert.hs

http://stackoverflow.com/questions/20568276/implement-insert-in-haskell-with-foldr
  /20570385#20570385
----

You need a [paramorphism](http://stackoverflow.com/a/13317563/849891) for that:

    para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
    foldr :: (a ->        b -> b) -> b -> [a] -> b
    
    para  c n (x : xs) = c x xs (para c n xs)
    foldr c n (x : xs) = c x    (foldr c n xs)
    para  c n []       = n
    foldr c n []       = n

with it,
 
    insert v xs = para (\x xs ys-> if v <= x then (v:x:xs) else (x:ys)) [v] xs

We can imitate paramorphisms with `foldr` over `init . tails`, as can be seen 
here: http://stackoverflow.com/questions/14403293/
 need-to-partition-a-list-into-lists-based-on-breaks-in-ascending-order-of-elemen/
 14451312#14451312.
____
Thus the solution is

    import Data.List (tails)

    insert v xs = foldr g [v] (init $ tails xs)
      where
        g xs@(x:_) ys | v <= x    = v : xs
                      | otherwise = x : ys
____
Another way to encode paramorphism is by creating nested functions chain, 
as seen in the [answer by Pedro Rodrigues](http://stackoverflow.com/a/20569505/849891),
to arrange for the *left-to-right* information flow:

    insert v xs = foldr g (const [v]) xs xs
      where
        g x f xs | v > x     = x : f (tail xs)
                 | otherwise = v : xs

    -- the visual aid to how this works, for list [a,b,c,d]:
    -- g a (g b (g c (g d (const [v])))) [a,b,c,d]

Unlike the version in his answer, this does not copy the rest of the list structure after 
the insertion point (which is made possible by virtue of paramorphism's ability to "eat the 
cake and have it too", i.e. by passing a second copy of the input list as the additional argument).