Dear Haskell users:
I am trying to define common functions with recursive combinators
avoiding recursive definitions. I have found some problems with
the "insert" function that inserts an element x in an ordered list xs
This function is used when you define insertion sort as "foldr insert []"
-- First attempt
insert::(Ord a)=>a->[a]->[a]
insert x = foldr (\x (y:ys) -> if x < y then x:y:ys
else y:x:ys) [x]
-- Problem:
-- If I try: ? head (insert 1 [2..])
-- I obtain "control stack overflow"
-- I could simulate it using a new combinator:
insert' e = newFoldr (\x y z -> if e < x then e:x:y
else x:z ) [e]
newFoldr::(a->[a]->b->b)->b->[a]->b
newFoldr f c [] = c
newFoldr f c (x:xs) = f x xs (newFoldr f c xs)
But I would like to use the combinators of Haskell prelude
(specially "foldr") The reason is that I think that we must
avoid new recursive combinators and reuse the existing ones.
If we need new ones, we must know which are the fundamental
combinators. I really think that "newfold" is not a
fundamental combinator, is it?
-- Another attempt could be to use the following definition
insert'' x xs = ls ++ (x:gs)
where (ls,gs) = span (<x) xs
-- But the '++' takes linear time with the size of 'ls'
I think that there must be an easy solution but in this
moment I can't see it.
Another question: Why is the "unfold" function not included in the
haskell prelude?
I think "unfold" is a fundamental combinator!
By the way, I think it was E. Meijer who said that
recursive definitions in Functional Languages were similar
to "goto's" in imperative languages
I would like to have the reference (if it exists)
Jose Emilio Labra Gayo
Dept. of Computer Science
Univ. of Oviedo, Spain
http://www.uniovi.es/~oviedo3/labra/
e-mail: [EMAIL PROTECTED]
