[Haskell-cafe] Are constructors strict?

[Daryoush Mehrtash]

Sebastian,

At high level, I understand the notion that thunks are about values and not
nondeterminism computation but I have been missing the isight in the code as
how this happens..  After reading it a few times and trying some
experiments.  This is my "layman" understanding of the problem...

It seems to boil down the that idea that when we have

do x <- e1
     e2

values in e1 is evaluated lazily, but, at least in naive coding, e2 has no
way of controlling e1, it just has to take what is dished out to it!

so in

do ys <- perm xs

assuming there are N permutation on xs we would lazily generate the
following

perm xs = p1 'mplus' p2 'mplus'  ... pn

where each of the Permutation are themselves evaluated lazily.

Again if I understand this correctly, the reason why sort in section 2.2 of
the paper is slow is that even though isSorted can determine that any
permutation that has its first two arguments as say (20,10....) is not
sorted, but the "perm xs" keeps generating  different permutation all
starting with (20,10...) and isSorted has to keep rejecting them.

So even-though for each permutation the code lazily looks at minimum number
of elements to rule out unsorted permutation, still the number of extra
permutation that are generated causes slow overall response.

Am I correct?

-- 
Daryoush

Weblog:  http://onfp.blogspot.com/ <http://perlustration.blogspot.com/>


On Sat, Jan 22, 2011 at 6:12 AM, Sebastian Fischer <fischer at nii.ac.jp>wrote:

> Hi Daryoush,
>
> On Fri, Jan 21, 2011 at 7:52 PM, Daryoush Mehrtash <dmehrtash at gmail.com>wrote:
>
>>
>>  loop = MonadPlus m => m Bool
>>>
>>  loop = loop
>>>
>>
>>> If we apply Just to loop as follows
>>>
>>
>>>  test2 :: MonadPlus m => m (Maybe Bool)
>>>
>>  test2 = loop >>= return . Just
>>>
>>
>>> the evaluation of test2 does not terminate because >>= has to evaluate
>>> loop. But this does not correctly reflect the behaviour in a functional
>>> logic language like Curry. For example, if you have a function that checks
>>> whether the outermost constructor of test2 is Just, the test is supposed to
>>> be successful. In the naive model for non-determinism this is not the case.
>>>
>>
>> Do I have to have MonadPlus m or would any other Monad class work the same
>> way?
>>
>
> I'm afraid, I don't quite get you question. Would you mind clarifying it
> with an example?
>
> Also, Jan, I don't understand your comment about continuation monads. Maybe
> I am a bit numb today.. What property do you mean do continuation monads
> have or not?
>
> Thanks,
> Sebastian
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110125/946ed4d9/attachment.htm>