[Haskell-cafe] Why is this strict in its arguments?

[Paulo J. Matos]

On Dec 4, 2007 10:00 PM, Neil Mitchell <ndmitchell at gmail.com> wrote:
> Hi
>
> > findAllPath :: (a -> Bool) -> (BTree a) -> [[a]]
> >       findAllPath pred = g where
> >           g (Leaf l) | pred l = [[l]]
> >           g (Branch lf r rt) | pred r = map (r:) $ (findAllPath pred
> > lf) ++ (findAllPath pred rt)
> >           g _  = []
> >
> > without even using maybe. However, 2 questions remained:
> > 1 - why is the first version strict in its arguments?
>
> Because in all call paths findAllPath will call g with its second
> argument. g will always evaluate (by pattern matching on) its value
> argument.
>

Wait! You're analyzing my second function and you're saying that it is
strict in its arguments?
Gee, that's bad. I questioned about the first one. The second seems to
be definitely lazy because I can use it on such big trees like I
showed. How come I can do this computation if like you said the
function is strict?

> > 2 - if it really is strict in its arguments, is there any automated
> > way to know when a function is strict in its arguments?
>
> Yes, strictness analysis is a very well studied subject -
> http://haskell.org/haskellwiki/Research_papers/Compilation#Strictness
> . Essentially, an argument is strict if passing _|_ for that value
> results in _|_. So to take your example, evaluating:
>
> findAllPath a _|_
> g _|_
> _|_
>
> Since g tests what value _|_ has, we get bottom.
>
> Thanks
>
> Neil
>
>
>



-- 
Paulo Jorge Matos - pocm at soton.ac.uk
http://www.personal.soton.ac.uk/pocm
PhD Student @ ECS
University of Southampton, UK