Re: [Haskell-cafe] Are constructors strict?
Hi, On 22.01.2011, at 08:12, Sebastian Fischer wrote: 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? I was wrong there. If there exist values x and y with x /= y and you have a function f such that f x /= f y then we have f _|_ = _|_ (at least if f is a sequential function). I thought this property might fail if x and y are functions but I was totally wrong. Therefore the laws mzero = f = mzero and return x = f = f x together with mzero /= mplus m n and mzero /= mplus (m = f) (n = f) for some m and n implies that we have _|_ = f = _|_ if = is sequential. Cheers, Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
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 fisc...@nii.ac.jpwrote: Hi Daryoush, On Fri, Jan 21, 2011 at 7:52 PM, Daryoush Mehrtash dmehrt...@gmail.comwrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
Hi Daryoush, On Fri, Jan 21, 2011 at 7:52 PM, Daryoush Mehrtash dmehrt...@gmail.comwrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
On 20.01.2011, at 22:18, Daryoush Mehrtash wrote: I am having hard time understanding the following paragraph in Purely functional Lazy non-deterministic programing paper http://www.cs.rutgers.edu/~ccshan/rational/lazy-nondet.pdf The problem with the naive monadic encoding of non-determinism is that the arguments to a constructor must be deterministic. If these arguments are themselves results of non-deterministic computations, these computations must be performed completely before we can apply the constructor to build a non-deterministic result. Why does the argument to constructors must be deterministic?WHy is it that thunks are not used in this case? If you use a monadic model for non-determinism in Haskell you use the standard constructors provided by Haskell and the bind operator to apply it to a non-deterministic (monadic) value. For example, consider the non-deterministic value coin defined as follows. coin :: MonadPlus m = m Bool coin = False `mplus` True To apply the constructor Just to this value you use the bind operator as follows. test :: MonadPlus m = m (Maybe Bool) test = coin = return . Just If you now consider the following definition. 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. Cheers, Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
sorry, forgot to cc cafe. On Fri, Jan 21, 2011 at 7:12 PM, Sebastian Fischer fisc...@nii.ac.jpwrote: Hi Daryoush, On Fri, Jan 21, 2011 at 6:18 AM, Daryoush Mehrtash dmehrt...@gmail.comwrote: I am having hard time understanding the following paragraph in Purely functional Lazy non-deterministic programing paper http://www.cs.rutgers.edu/~ccshan/rational/lazy-nondet.pdf The problem with the naive monadic encoding of non-determinism is that the arguments to a constructor must be deterministic. If these arguments are themselves results of non-deterministic computations, these computations must be performed completely before we can apply the constructor to build a non-deterministic result. Why does the argument to constructors must be deterministic? Because of the type of the constructor. Say you want to compute a list of Ints nondeterministically (like in the paper). Than the first argument of the (:) constructurs in the result must be an Int. A nondeterministic computation that yields an Int has type (m Int) for some nondeterminism monad (for example, it has type [Int] in the list monad). That the (:) constructur is polymorphic and would allow to make a value of type [m Int], is a coincidence and does not help to make a value of type (m [Int]). WHy is it that thunks are not used in this case? Thunks do not model nondeterminism, only laziness. Did that help you understand? Regards, Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
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? -- Daryoush Weblog: http://perlustration.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
On 21.01.2011, at 11:52, Daryoush Mehrtash wrote: Do I have to have MonadPlus m or would any other Monad class work the same way? Not all monad instances satisfy undefined = return . Just = undefined if that's what you are asking for. For example, consider the identity monad. instance Monad Identity where return = Identity m = k = k (runIdentity m) Then we have undefined = return . Just = undefined = Identity . Just = Identity (Just undefined) /= undefined If = performs pattern matching on its first argument like most instances do then you get undefined = return . Just = undefined. I think that the monadplus laws mplus m n = f = mplus (m = f) (n = f) called (Ldistr) in the paper and mzero = f = mzero called (Lzero) in the paper imply undefined = return . Just = undefined At least if you have mzero /= mplus m n which is quite desirable. I don't think that this holds for continuation based monads. But Sebastian will most certainly know better as he is one of the authors of the paper. Cheers, Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Are constructors strict?
I am having hard time understanding the following paragraph in Purely functional Lazy non-deterministic programing paper http://www.cs.rutgers.edu/~ccshan/rational/lazy-nondet.pdf The problem with the naive monadic encoding of non-determinism is that the arguments to a constructor must be deterministic. If these arguments are themselves results of non-deterministic computations, these computations must be performed completely before we can apply the constructor to build a non-deterministic result. Why does the argument to constructors must be deterministic?WHy is it that thunks are not used in this case? Thanks -- Daryoush Weblog: http://onfp.blogspot.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Are constructors strict?
Hello Daryoush, That is a good question, and depends on distinguishing between laziness and nondeterminism. Suppose I have a normal, lazily evaluated list: [1,2...] There are thunks used in this case, but the end result is fully deterministic: the next will always be 3, and then 4, and so on. So thunks don't give us nondeterminism; we need some other mechanism (whether it's another list encoding the choices, or a more sophisticated backtracking monad.) Edward ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
