Thanks to Matt Harden <[EMAIL PROTECTED]>
and Carsten Schultz <[EMAIL PROTECTED]>
for their helpful comments on
zipRem :: [a] -> [b] -> [(a,b),[a],[b])
-- zip preserving remainder lists
zipRem [] ys = ([], [], ys)
zipRem xs [] = ([], xs, [])
zipRem (x:xs) (y:ys) = case zipRem xs ys
of
(ps,xs',ys') -> ((x,y):ps, xs', ys')
I complained recently on that it compiles into a space hungry thing.
Mutt Harden says that the matter is in that this recursion is not a
tail-recursion. And gives a nice tail-recursive version of the
algorithm, using accumulator function of composed (x:).
If so, then, how many Standard Library functions can improve this
way?
Generally, it is too easy to write a space eater in Haskell.
The compilers do not care much.
The below function is not of Standard, but presents certain simplest
example (sorry if it is wrongly cited):
allMaybes :: [Maybe a] -> Maybe [a]
allMaybes [] = Just []
allMaybes (Nothing:_ ) = Nothing
allMaybes (Just x :ms) = case allMaybes ms of
Nothing -> Nothing
Just xs -> Just (x:xs)
Now, isJust $ allMaybes $ map Just [1..n]
is likely to need the _stack_ proportional to n.
Instead,
am ms = a [] ms where a xs [] = Just $ reverse xs
a _ (Nothing:_ ) = Nothing
a xs (Just x :ms) = a (x:xs) ms
will require a constant stack.
Again, why the compilers themself do not understand simplest
possibilities to convert to the tail recursion?
Maybe, Carsten Schultz gives some answer:
> your zipRem [..]
> is stricter than you probably want it to be: Due to the use of
> case you have, e.g.,
> zipRem (0:_|_) [0] = _|_.
> Try instead
> [..]
> zipRem2 (x:xs) (y:ys) = ((x,y):ps, xs', ys') where
> (ps, xs', ys') = zipRem2 xs ys
> [..]
So, maybe, the compiler converts zipRem2 into tail recursion,
and cannot do this to zipRem due to the different meaning of
`case' and `where' (`let').
Do I understand right?
head $ tuple31 $ zipRem2 (1:undefined) --> 1
head $ tuple31 $ zipRem (1:undefined) --> undefined
Why Haskell is so? Why case zipRem undefined []
of
(ps,xs',ys') -> ((x,y):ps, xs', ys')
does not allow the result of zipRem undefined []
to be of (ps,xs',ys')
(which type is declared in zipRem) ?
And `let', `where' do allow this.
Now, the simpler example:
f [] = []
f (x:xs) = case f xs of ps -> (x,x):ps
head $ f (1:undefined) --> (1,1)
Here `case' behaves differently. I am about totally confused.
The past century was not enough to study the basic Haskell.
Maybe, the constructor (,,) in the zipRem pattern forces some kind
of strictness, I do not know.
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
