I really don't understand this

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

I really don't understand this

Jean-Marc Alliot
I apologize if my question is stupid, but here is a simple Haskell
program which never stops.

However, if I comment the line (which is apparently useless):
v<-acc
The program works like a charm...

I am using GHC 8.0.2 (debian sid) and multiset 0.3.3. If anyone has an
idea,  I would gladly hear it.

Thanks in advance

PS: don't try to understand what the program is doing; it is just the
reduction to a few lines of a much larger code; I have tried to find a
smaller subset which is not working "properly".
  PPS: The program can also be downloaded from:
http://www.alliot.fr/tmp/example.hs

import qualified Data.IntMultiSet as IMS

b :: IMS.IntMultiSet
b = IMS.fromList ([1, 2, 3, 4])

search :: IMS.IntMultiSet -> Int -> IO Bool
search mynumbers nb = ins mynumbers (return False)
   where
     ins numbers acc = do
       v <- acc
       IMS.fold
         (\x acc1 ->
            let numbers2 = IMS.delete x numbers
             in IMS.fold
                  (\y acc2 ->
                     let numbers3 = IMS.delete y numbers2
                         res = x + y
                      in if res == nb
                           then (return True)
                           else ins (IMS.insert res numbers3) acc2)
                  acc1
                  numbers2)
         acc
         numbers

main = do
   v <- search b 999999999
   print v
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: I really don't understand this

Li-yao Xia-2
Bonjour Jean-Marc,

"acc" contains the computation of the whole search up to a point.
Calling it once (as part of the fold) makes it grow linearly in the size
of the search space, but calling it twice (once more as "v <- acc")
makes it grow exponentially.

Cordialement,
Li-yao

On 01/23/2018 08:35 AM, Jean-Marc Alliot wrote:

> I apologize if my question is stupid, but here is a simple Haskell
> program which never stops.
>
> However, if I comment the line (which is apparently useless):
> v<-acc
> The program works like a charm...
>
> I am using GHC 8.0.2 (debian sid) and multiset 0.3.3. If anyone has an
> idea,  I would gladly hear it.
>
> Thanks in advance
>
> PS: don't try to understand what the program is doing; it is just the
> reduction to a few lines of a much larger code; I have tried to find a
> smaller subset which is not working "properly".
>   PPS: The program can also be downloaded from:
> http://www.alliot.fr/tmp/example.hs
>
> import qualified Data.IntMultiSet as IMS
>
> b :: IMS.IntMultiSet
> b = IMS.fromList ([1, 2, 3, 4])
>
> search :: IMS.IntMultiSet -> Int -> IO Bool
> search mynumbers nb = ins mynumbers (return False)
>    where
>      ins numbers acc = do
>        v <- acc
>        IMS.fold
>          (\x acc1 ->
>             let numbers2 = IMS.delete x numbers
>              in IMS.fold
>                   (\y acc2 ->
>                      let numbers3 = IMS.delete y numbers2
>                          res = x + y
>                       in if res == nb
>                            then (return True)
>                            else ins (IMS.insert res numbers3) acc2)
>                   acc1
>                   numbers2)
>          acc
>          numbers
>
> main = do
>    v <- search b 999999999
>    print v
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: I really don't understand this

Jean-Marc Alliot
Thank you very much for your answer, but I still don't get it (I might
be not bright enough :-))

I rewrote the program to suppress all syntactic sugar; for me, the value
of the first argument of >>= is never used, so I can't see why it
changes anything to put acc as the first argument or anything else (such
as return false for example...).

I would really appreciate a pointer to a chapter of any manual or
introduction to Haskell which would be able to explain why with acc as
first argument of (>==) the program runs at least 2 hours (I stopped it
after 2 hours) and with (return False) it takes less than one second,
while the actual value of the first argument of (>>=) is meaningless.

Thanks again for answering

import qualified Data.IntMultiSet as IMS

b :: IMS.IntMultiSet
b = IMS.fromList ([1, 2, 3, 4])

search2 :: IMS.IntMultiSet -> Int -> IO Bool
search2 mynumbers nb = ins mynumbers (return False)
   where
     ins numbers acc =
       (>>=)
         acc
         (\_ ->
            IMS.fold
              (\x acc1 ->
                 let numbers2 = IMS.delete x numbers
                  in IMS.fold
                       (\y acc2 ->
                          let numbers3 = IMS.delete y numbers2
                              res = x + y
                           in if res == nb
                                then (return True)
                                else ins (IMS.insert res numbers3) acc2)
                       acc1
                       numbers2)
              acc
              numbers)

main = do
   v <- search2 b 999999999
   print v


Le 23/01/2018 à 16:03, Li-yao Xia a écrit :

> Bonjour Jean-Marc,
>
> "acc" contains the computation of the whole search up to a point.
> Calling it once (as part of the fold) makes it grow linearly in the
> size of the search space, but calling it twice (once more as "v <-
> acc") makes it grow exponentially.
>
> Cordialement,
> Li-yao
>
> On 01/23/2018 08:35 AM, Jean-Marc Alliot wrote:
>> I apologize if my question is stupid, but here is a simple Haskell
>> program which never stops.
>>
>> However, if I comment the line (which is apparently useless):
>> v<-acc
>> The program works like a charm...
>>
>> I am using GHC 8.0.2 (debian sid) and multiset 0.3.3. If anyone has
>> an idea,  I would gladly hear it.
>>
>> Thanks in advance
>>
>> PS: don't try to understand what the program is doing; it is just the
>> reduction to a few lines of a much larger code; I have tried to find
>> a smaller subset which is not working "properly".
>>   PPS: The program can also be downloaded from:
>> http://www.alliot.fr/tmp/example.hs
>>
>> import qualified Data.IntMultiSet as IMS
>>
>> b :: IMS.IntMultiSet
>> b = IMS.fromList ([1, 2, 3, 4])
>>
>> search :: IMS.IntMultiSet -> Int -> IO Bool
>> search mynumbers nb = ins mynumbers (return False)
>>    where
>>      ins numbers acc = do
>>        v <- acc
>>        IMS.fold
>>          (\x acc1 ->
>>             let numbers2 = IMS.delete x numbers
>>              in IMS.fold
>>                   (\y acc2 ->
>>                      let numbers3 = IMS.delete y numbers2
>>                          res = x + y
>>                       in if res == nb
>>                            then (return True)
>>                            else ins (IMS.insert res numbers3) acc2)
>>                   acc1
>>                   numbers2)
>>          acc
>>          numbers
>>
>> main = do
>>    v <- search b 999999999
>>    print v
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: I really don't understand this

Li-yao Xia-2
Hi,

On 01/23/2018 02:39 PM, Jean-Marc Alliot wrote:
> Thank you very much for your answer, but I still don't get it (I might
> be not bright enough :-))
>

Not at all! This is definitely not an obvious problem.

> I rewrote the program to suppress all syntactic sugar; for me, the value
> of the first argument of >>= is never used, so I can't see why it
> changes anything to put acc as the first argument or anything else (such
> as return false for example...).
>

You can erase (acc :: IO Bool) only if acc is in fact pure (i.e., acc =
return b), but how would GHC deduce such a fact?

- inlining could take care of it on a case-by-case basis at each call
site, but ins is recursive, which prevents inlining;

- a more general solution for recursive definitions might be some kind
of static analysis, that GHC doesn't do;

- using Identity instead of IO, then all computations must be pure, and
in fact the optimization would apply automatically as a consequence of
the lazy (>>=) for Identity.

> I would really appreciate a pointer to a chapter of any manual or
> introduction to Haskell which would be able to explain why with acc as
> first argument of (>==) the program runs at least 2 hours (I stopped it
> after 2 hours) and with (return False) it takes less than one second,
> while the actual value of the first argument of (>>=) is meaningless.
>

I don't have any good pointers unfortunately.

But it may help to expand the folds.

ins {1,2,3} acc = do
   acc
   ins {1+2,3} (ins {1+3,2} (ins {2+1,3} (... (ins {3+2, 1} acc))))

For the first recursive call to ins...

ins {1+2,3} acc1 = do
   acc1
   ins {1+2+3} (ins {3+1+2} acc1)

... substitute that in the former (acc1 = ins {1+3,2} (ins {2+1,3} (...
acc)))

ins {1,2,3} acc = do
   acc
   (ins {1+3,2} (... acc))
   ins {1+2+3} (ins {3+1+2} (ins {1+3,2} (... acc)))

etc.

Li-yao
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: I really don't understand this

Jean-Marc Alliot
First thanks again for the answer, I really appreciate.

However, I am still a little bit in doubt, so I decided to write an
ocaml search2 function which is almost an exact copy/paste of the
Haskell function, including an IO monad implemented in ocaml (included
below; I am much more fluent in caml that I have been using for 20 years
than I am in Haskell, as you might have guessed).

In ocaml, there is no problem at all and everything is running as I
expect it to run. I can access and even print the value of acc without
modifying the behaviour of the program.

The main difference I am aware of is that Haskell is lazy while ocaml is
not. So is my interpretation correct if I say that Hakell lazyness is
the reason why the Haskell program behaves "oddly" (according to my
standards of course, there is no judgement value here)? And if it is so,
is it possible to force the evaluation in order to have a program which
doesn't run forever just because I am accessing an object?

I presume I am still confused and I might be wrong, so thanks again for
helping.



module IOMonad = struct
   type 'a t = IO of 'a;;
   let return x = IO x;;
   let (>>=) (IO m) (f : ('a -> 'b t)) = (f m);;
end;;
open IOMonad;;

module IMS = CCMultiSet.Make(struct type t = int let compare = compare  
end);;
let delete x s = IMS.remove s x;;
let insert x s = IMS.add s x;;
let fold f b s =
   let f2 b n t = f t b in
   IMS.fold s b f2;;
let fromlist  = IMS.of_list ;;

let search2 mynumbers nb =
   let rec ins numbers acc =
     (>>=)
       acc
       (fun v -> (* Printf.printf "%b\n" v; *)
         fold
           (fun x acc1 ->
             let numbers2 = delete x numbers
             in fold
                  (fun y acc2 ->
                    let numbers3 = delete y numbers2
                    and res = x + y
                    in if res = nb
                       then (return true)
                       else ins (insert res numbers3) acc2)
                  acc1
                  numbers2)
           acc
           numbers) in
   ins mynumbers (return false);;

let b = fromlist [1;2;3;4];;
let main =
   (>>=)
     (search2 b 99999999)
     (fun v -> return
       (if v then Printf.printf "True\n"
       else Printf.printf "False\n"));;



Le 23/01/2018 à 22:08, Li-yao Xia a écrit :

> Hi,
>
> On 01/23/2018 02:39 PM, Jean-Marc Alliot wrote:
>> Thank you very much for your answer, but I still don't get it (I
>> might be not bright enough :-))
>>
>
> Not at all! This is definitely not an obvious problem.
>
>> I rewrote the program to suppress all syntactic sugar; for me, the
>> value of the first argument of >>= is never used, so I can't see why
>> it changes anything to put acc as the first argument or anything else
>> (such as return false for example...).
>>
>
> You can erase (acc :: IO Bool) only if acc is in fact pure (i.e., acc
> = return b), but how would GHC deduce such a fact?
>
> - inlining could take care of it on a case-by-case basis at each call
> site, but ins is recursive, which prevents inlining;
>
> - a more general solution for recursive definitions might be some kind
> of static analysis, that GHC doesn't do;
>
> - using Identity instead of IO, then all computations must be pure,
> and in fact the optimization would apply automatically as a
> consequence of the lazy (>>=) for Identity.
>
>> I would really appreciate a pointer to a chapter of any manual or
>> introduction to Haskell which would be able to explain why with acc
>> as first argument of (>==) the program runs at least 2 hours (I
>> stopped it after 2 hours) and with (return False) it takes less than
>> one second, while the actual value of the first argument of (>>=) is
>> meaningless.
>>
>
> I don't have any good pointers unfortunately.
>
> But it may help to expand the folds.
>
> ins {1,2,3} acc = do
>   acc
>   ins {1+2,3} (ins {1+3,2} (ins {2+1,3} (... (ins {3+2, 1} acc))))
>
> For the first recursive call to ins...
>
> ins {1+2,3} acc1 = do
>   acc1
>   ins {1+2+3} (ins {3+1+2} acc1)
>
> ... substitute that in the former (acc1 = ins {1+3,2} (ins {2+1,3}
> (... acc)))
>
> ins {1,2,3} acc = do
>   acc
>   (ins {1+3,2} (... acc))
>   ins {1+2+3} (ins {3+1+2} (ins {1+3,2} (... acc)))
>
> etc.
>
> Li-yao

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: I really don't understand this

Li-yao Xia-2
Hi,

On 01/24/2018 12:02 PM, Jean-Marc Alliot wrote:
> First thanks again for the answer, I really appreciate.
>

You're welcome, I'm happy to help!
> module IOMonad = struct
>    type 'a t = IO of 'a;;
>    let return x = IO x;;
>    let (>>=) (IO m) (f : ('a -> 'b t)) = (f m);;
> end;;
> open IOMonad;;

The closest thing to Haskell's (IO a) in OCaml is (unit -> 'a).

module IOMonad = struct
   type 'a t = unit -> 'a
   let return x = fun () -> x
   let (>>=) m f = fun () -> f (m ()) ()
end

I believe that definition will result in the same looping behavior as
with the original Haskell program.

It's not really a matter of laziness, but more of (im)purity. In OCaml,
functions can have side effects. In Haskell, we must write pure
functions that return an effectful computation as a value.
In particular, we have the following property in Haskell:

     let a = print 1 in a >> a  -- a :: IO ()

is equivalent to

     print 1 >> print 1

because "a" stands for the computation that prints 1 and returns ().

Whereas in OCaml:

     let a = print_int 1 in a; a

is not equivalent to

     print_int 1; print_int 1

here "a" just stands for (), and the effect is performed before it is
evaluated.

But we can define (print : int -> IO.t ()) as (let print n () =
print_int n) in OCaml, with compositional properties similar to
Haskell's print.

Li-yao
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.