Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. exceptions and stacks (Emmanuel Touzery)
2. Re: exceptions and stacks (Ozgur Akgun)
3. Re: exceptions and stacks (Ozgur Akgun)
4. Re: Trying to write netwire combiner similar to multicast
(Nathan H?sken)
5. Re: Pattern guard inside function (Bob Hutchison)
6. Re: Trying to write netwire combiner similar to multicast
(Ertugrul S?ylemez)
7. Re: Beginners Digest, Vol 53, Issue 7 (Patrick Lynch)
----------------------------------------------------------------------
Message: 1
Date: Tue, 06 Nov 2012 12:44:07 +0100
From: Emmanuel Touzery <[email protected]>
Subject: [Haskell-beginners] exceptions and stacks
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hello,
I'm getting really frustrated by error handling in haskell. By this
I mean "assert"-like errors. Which means, something that should never
happen, happens. This will happen in the development and deployment of
software of any size.
When coding the feature you'll say, I don't need to handle the
"Nothing" case, because it will never happen, or almost never, and this
is not critical production software.
But if one day it happens you find yourself with a several thousand
lines program and all you have to debug is the input data (most of the
time anyway, sometimes not even that) and this error message (for instance):
*** Exception: Prelude.head: empty list
And you don't know even, did you call "head" or maybe a library you
are using called it.
This is really poor compared to what Java, python and others
offers. I can understand that it's difficult to provide a stack trace,
especially with lazy evaluation, but at least the function name and
maybe a line number... Actually I don't know why it would be so
difficult to also give me the values of the parameters of the
function... using print and if it's a pure function it intuitively
doesn't seem difficult.
I've tried ghci with :trace and ":set -fbreak-on-exception" and I
got nowhere. It breaks in things which are not important (I have no idea
where it breaks, it claims an exception was thrown, maybe but not in my
code and it never reaches my code for sure). After hitting ":continue"
many times, I get to my exception and there I didn't manage to get
useful information (:hist never printed me anything).
But I would like not to have to use ghci at all. And to avoid
having to write all over the place in my code these "else" and case
situations for things I assume are impossible (these are cases I would
not write in other modern languages).
This is a feature for which I would be ready to pay a 50% speed
penalty and 50% memory use penalty.
I understand if it's the haskell way of writing all those else
clauses... But I think in that case it really makes it compare
negatively to other languages. It would be a real minus in my opinion
(including to code readability).
I have read (quickly) those but didn't find the solution there:
http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/ghci-debugger.html
http://book.realworldhaskell.org/read/error-handling.html
Any advice will be welcome! I really hope I missed something.
Emmanuel
------------------------------
Message: 2
Date: Tue, 6 Nov 2012 12:02:11 +0000
From: Ozgur Akgun <[email protected]>
Subject: Re: [Haskell-beginners] exceptions and stacks
To: Emmanuel Touzery <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CALzazPCAAV2_8EDzfUOwncpSj-4d24oCbBFt5hhow=qaypb...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Emmanuel,
It is indeed good practice to write total programs in general. However, I
understand the need for stack traces in practice.
There are some slides by Simon Marlow on the issue, ironically using your
example in the title.
In short: check the -xc flag in
http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/runtime-control.html
Hope this helps,
Ozgur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121106/7e633967/attachment-0001.htm>
------------------------------
Message: 3
Date: Tue, 6 Nov 2012 12:02:56 +0000
From: Ozgur Akgun <[email protected]>
Subject: Re: [Haskell-beginners] exceptions and stacks
To: Emmanuel Touzery <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<calzazpbdg1vz9wqd2wrdgyp878rxfuluwsw9hcpcoalj46t...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On 6 November 2012 12:02, Ozgur Akgun <[email protected]> wrote:
> There are some slides by Simon Marlow on the issue, ironically using your
> example in the title.
>
Sorry, forgot to add the link to slides:
http://community.haskell.org/~simonmar/slides/HIW11.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121106/baf31244/attachment-0001.htm>
------------------------------
Message: 4
Date: Tue, 06 Nov 2012 13:24:42 +0100
From: Nathan H?sken <[email protected]>
Subject: Re: [Haskell-beginners] Trying to write netwire combiner
similar to multicast
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 11/06/2012 02:44 AM, Ertugrul S?ylemez wrote:
> Nathan H?sken <[email protected]> wrote:
>
>>> Also your interface seems very unsafe to me. I suggest the
>>> following interface instead:
>>>
>>> shrinking :: (Monad m) => [Wire e m a b] -> Wire e m a [b]
>>>
>>> Then normally 'a' could be something like Map K A.
>>
>> That would mean, the individual wires have to know there own id?!?
>> Mmmh, I will try to keep this bookkeeping out of the wires with this
>> interface:
>>
>> shrinking :: (Monad m) => [Wire e m a b] -> Wire e m (Map Int a)
>> (Int,b)
>>
>> shrinking will assign the ids to the wires and returns them with the
>> result. I will see where this gets me ... :).
>
> The problem with such an interface is the inflexibility. Notice that
> removing a subwire will change the numbering of all subsequent wires.
> The interface I suggested follows this basic idea:
>
> shrinking ::
> (Monad m)
> => [(a' -> a, Wire e m a b)]
> -> Wire e m a' b
>
That should be ".. -> Wire e m a' [b]", correct?
> The reasoning is that this way you disconnect the individual values from
> the positions in the subwire list. This will also make writing the
> combinator a bit simpler. If you will here is an interesting
> alternative:
>
> data Subwire e m a b =
> forall a'. Subwire (a -> a') (Wire e m a' b)
>
> shrinking :: (Monad m) => [Subwire e m a b] -> Wire e m a b
>
Ohh, the scary forall keyword :).
Here it does nothing but hide the a' type from the type signature, is
that correct?
Thanks!
Nathan
------------------------------
Message: 5
Date: Tue, 6 Nov 2012 07:41:33 -0500
From: Bob Hutchison <[email protected]>
Subject: Re: [Haskell-beginners] Pattern guard inside function
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
On 2012-10-31, at 1:22 PM, Bob Hutchison <[email protected]> wrote:
> Hi,
>
> On 2012-10-31, at 10:02 AM, Nathan H?sken <[email protected]> wrote:
>
>> Hey
>>
>> I have a function which originaly locked like this:
>>
>> collInfo :: Rect -> Rect -> Maybe CollInfo
>> collInfo (Rect x1 y1 w1 h1) (Rect x2 y2 w2 h2)
>> | x1 + w1 < x2 = Nothing
>> | x1 > x2 + w2 = Nothing
>> | y1 + h1 < y2 = Nothing
>> | y1 > y2 + h2 = Nothing
>> | otherwiese = Just $ makeCollInfo r1 r2
>>
>> Now I want to refactor it to take Maybe input values
>>
>> collInfo' :: Maybe Rect -> Maybe Rect -> Maybe CollInfo
>> collInfo' mr1 mr2 =
>> r1 <- mr1
>> r2 <- mr2
>> collInfo r1 r2
>>
>> This is fine, but I would like to write it using only one function. Is
>> there any possibility I can remove collInfo and merge its body into
>> collInfo' and still somehow use the guards (and not a bunch of ifs)?
>
> maybe like:
>
> collInfo'' :: Maybe Rect -> Maybe Rect -> Maybe CollInfo
> collInfo'' (Just r1@(Rect x1 y1 w1 h1)) (Just r2@(Rect x2 y2 w2 h2))
> | x1 + w1 < x2 = Nothing
> | x1 > x2 + w2 = Nothing
> | y1 + h1 < y2 = Nothing
> | y1 > y2 + h2 = Nothing
> | otherwise = Just $ makeCollInfo r1 r2
> collInfo'' _ _ = Nothing
Here's another variation using Maybe as an applicative functor:
collInfo''' :: Maybe Rect -> Maybe Rect -> Maybe CollInfo
collInfo''' r1 r2 = join $ collInfo <$> r1 <*> r2
The join is in there to get rid a Maybe in (Maybe (Maybe _)). There's probably
a way to avoid that but I don't know what it is? I'm learning this stuff myself.
Cheers,
Bob
------------------------------
Message: 6
Date: Tue, 6 Nov 2012 16:00:01 +0100
From: Ertugrul S?ylemez <[email protected]>
Subject: Re: [Haskell-beginners] Trying to write netwire combiner
similar to multicast
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
Nathan H?sken <[email protected]> wrote:
> > The problem with such an interface is the inflexibility. Notice
> > that removing a subwire will change the numbering of all subsequent
> > wires. The interface I suggested follows this basic idea:
> >
> > shrinking ::
> > (Monad m)
> > => [(a' -> a, Wire e m a b)]
> > -> Wire e m a' b
>
> That should be ".. -> Wire e m a' [b]", correct?
Yes, of course.
> > The reasoning is that this way you disconnect the individual values
> > from the positions in the subwire list. This will also make writing
> > the combinator a bit simpler. If you will here is an interesting
> > alternative:
> >
> > data Subwire e m a b =
> > forall a'. Subwire (a -> a') (Wire e m a' b)
> >
> > shrinking :: (Monad m) => [Subwire e m a b] -> Wire e m a b
>
> Ohh, the scary forall keyword :).
> Here it does nothing but hide the a' type from the type signature, is
> that correct?
It also localizes error messages to where your subwire is defined.
Greets,
Ertugrul
--
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121106/9d0c71e0/attachment-0001.pgp>
------------------------------
Message: 7
Date: Tue, 06 Nov 2012 10:19:08 -0500
From: "Patrick Lynch" <[email protected]>
Subject: Re: [Haskell-beginners] Beginners Digest, Vol 53, Issue 7
To: <[email protected]>
Message-ID: <A15045E335BF413EBF6B9BCE818AFDA1@UserPC>
Content-Type: text/plain; format=flowed; charset=iso-8859-1;
reply-type=original
Can anyone recommend a way of using Haskell on the web?
----- Original Message -----
From: <[email protected]>
To: <[email protected]>
Sent: Monday, November 05, 2012 4:27 PM
Subject: Beginners Digest, Vol 53, Issue 7
> Send Beginners mailing list submissions to
> [email protected]
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://www.haskell.org/mailman/listinfo/beginners
> or, via email, send a message with subject or body 'help' to
> [email protected]
>
> You can reach the person managing the list at
> [email protected]
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Beginners digest..."
>
>
> Today's Topics:
>
> 1. Double usage of a wire (arrow) (Nathan H?sken)
> 2. Trying to write netwire combiner similar to multicast
> (Nathan H?sken)
> 3. Re: Double usage of a wire (arrow) (Ertugrul S?ylemez)
> 4. Re: Trying to write netwire combiner similar to multicast
> (Ertugrul S?ylemez)
> 5. Re: Trying to write netwire combiner similar to multicast
> (Nathan H?sken)
> 6. Missing termination rule for recursive function (Oscar Benjamin)
> 7. Re: Missing termination rule for recursive function
> (Daniel Fischer)
> 8. Re: Missing termination rule for recursive function
> (Jay Sulzberger)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 05 Nov 2012 15:12:00 +0100
> From: Nathan H?sken <[email protected]>
> Subject: [Haskell-beginners] Double usage of a wire (arrow)
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Hey,
>
> If I double use an arrow (in this example a wire from netwire) like this:
>
> objectWire :: WireP [Collision] Object
> objectWire = (Object <$> integral_ initPos) . speedWire <*> speedWire
>
> will it be double evaluated, or can the compiler optimize this to
> evaluate speedWire only once?
>
> Thanks!
> Nathan
>
>
>
> ------------------------------
>
> Message: 2
> Date: Mon, 05 Nov 2012 17:04:51 +0100
> From: Nathan H?sken <[email protected]>
> Subject: [Haskell-beginners] Trying to write netwire combiner similar
> to multicast
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Hey,
>
> I am trying to write a netwire combiner similar to multicast. The only
> difference is that when one of the wires inihibts, I want to remove it
> from the list.
>
> So this is my attempt:
>
> manager :: (Monad m) => [Wire e m a b] -> Wire e m [a] [b]
> manager ws' = mkGen $ \dt xs' -> do
> res <- mapM (\(w,x) -> stepWire w dt x) $ zip ws' xs'
> let filt (Left a, b) = Just (a, b)
> filt _ = Nothing
> resx = mapMaybe filt res
> return (Left $ (fmap fst) resx,manager (fmap snd resx))
>
> ghc gives this compiler error:
>
> BreakoutImproved.hs:90:62:
> Couldn't match type `e' with `[e]'
> `e' is a rigid type variable bound by
> the type signature for
> manager :: Monad m => [Wire e m a b] -> Wire e m [a] [b]
> at BreakoutImproved.hs:85:1
> Expected type: [(e, Wire [e] m a b)]
> Actual type: [(e, Wire e m a b)]
> In the second argument of `fmap', namely `resx'
> In the first argument of `manager', namely `(fmap snd resx)'
>
> Now this, I do not get.
> Why does manager expect an argument of type [(e, Wire [e] m a b)].
> The type signature clearly says [(e, Wire e m a b)] (which is what it is
> getting).
>
> Thanks!
> Nathan
>
>
>
> ------------------------------
>
> Message: 3
> Date: Mon, 5 Nov 2012 17:22:48 +0100
> From: Ertugrul S?ylemez <[email protected]>
> Subject: Re: [Haskell-beginners] Double usage of a wire (arrow)
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset="utf-8"
>
> Nathan H?sken <[email protected]> wrote:
>
>> If I double use an arrow (in this example a wire from netwire) like
>> this:
>>
>> objectWire :: WireP [Collision] Object
>> objectWire = (Object <$> integral_ initPos) . speedWire <*> speedWire
>>
>> will it be double evaluated, or can the compiler optimize this to
>> evaluate speedWire only once?
>
> It will be double-evaluated. To prevent this you can use the Arrow
> interface:
>
> proc x' -> do
> x <- speedWire -< x'
> {- ... use x ... -}
>
> However, in WireP it's guaranteed that you get the same result, so for
> code conciseness you can still have speedWire twice, if sacrificing some
> speed is not too big an issue.
>
>
> Greets,
> Ertugrul
>
> --
> Not to be or to be and (not to be or to be and (not to be or to be and
> (not to be or to be and ... that is the list monad.
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name: signature.asc
> Type: application/pgp-signature
> Size: 836 bytes
> Desc: not available
> URL:
> <http://www.haskell.org/pipermail/beginners/attachments/20121105/018fec91/attachment-0001.pgp>
>
> ------------------------------
>
> Message: 4
> Date: Mon, 5 Nov 2012 17:29:49 +0100
> From: Ertugrul S?ylemez <[email protected]>
> Subject: Re: [Haskell-beginners] Trying to write netwire combiner
> similar to multicast
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset="utf-8"
>
> Nathan H?sken <[email protected]> wrote:
>
>> I am trying to write a netwire combiner similar to multicast. The only
>> difference is that when one of the wires inihibts, I want to remove it
>> from the list.
>>
>> So this is my attempt:
>>
>> manager :: (Monad m) => [Wire e m a b] -> Wire e m [a] [b]
>> manager ws' = mkGen $ \dt xs' -> do
>> res <- mapM (\(w,x) -> stepWire w dt x) $ zip ws' xs'
>> let filt (Left a, b) = Just (a, b)
>> filt _ = Nothing
>> resx = mapMaybe filt res
>> return (Left $ (fmap fst) resx,manager (fmap snd resx))
>
> Notice that Left means inhibition. You seem to be filtering out
> produced results and trying to keep only the inhibition values, which of
> course does not make much sense and triggers the type error you are
> seeing.
>
> Also your interface seems very unsafe to me. I suggest the following
> interface instead:
>
> shrinking :: (Monad m) => [Wire e m a b] -> Wire e m a [b]
>
> Then normally 'a' could be something like Map K A.
>
>
> Greets,
> Ertugrul
>
> --
> Not to be or to be and (not to be or to be and (not to be or to be and
> (not to be or to be and ... that is the list monad.
> -------------- next part --------------
> A non-text attachment was scrubbed...
> Name: signature.asc
> Type: application/pgp-signature
> Size: 836 bytes
> Desc: not available
> URL:
> <http://www.haskell.org/pipermail/beginners/attachments/20121105/35a4df3f/attachment-0001.pgp>
>
> ------------------------------
>
> Message: 5
> Date: Mon, 05 Nov 2012 18:05:24 +0100
> From: Nathan H?sken <[email protected]>
> Subject: Re: [Haskell-beginners] Trying to write netwire combiner
> similar to multicast
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> On 11/05/2012 05:29 PM, Ertugrul S?ylemez wrote:
>> Nathan H?sken <[email protected]> wrote:
>>
>>> I am trying to write a netwire combiner similar to multicast. The only
>>> difference is that when one of the wires inihibts, I want to remove it
>>> from the list.
>>>
>>> So this is my attempt:
>>>
>>> manager :: (Monad m) => [Wire e m a b] -> Wire e m [a] [b]
>>> manager ws' = mkGen $ \dt xs' -> do
>>> res <- mapM (\(w,x) -> stepWire w dt x) $ zip ws' xs'
>>> let filt (Left a, b) = Just (a, b)
>>> filt _ = Nothing
>>> resx = mapMaybe filt res
>>> return (Left $ (fmap fst) resx,manager (fmap snd resx))
>>
>> Notice that Left means inhibition (...).
>
> I was sure right meant inhibition ... thanks!
>
>> Also your interface seems very unsafe to me. I suggest the following
>> interface instead:
>>
>> shrinking :: (Monad m) => [Wire e m a b] -> Wire e m a [b]
>>
>> Then normally 'a' could be something like Map K A.
>
> That would mean, the individual wires have to know there own id?!?
> Mmmh, I will try to keep this bookkeeping out of the wires with this
> interface:
>
> shrinking :: (Monad m) => [Wire e m a b] -> Wire e m (Map Int a) (Int,b)
>
> shrinking will assign the ids to the wires and returns them with the
> result. I will see where this gets me ... :).
>
> Regards,
> Nathan
>
>
>
>
>
> ------------------------------
>
> Message: 6
> Date: Mon, 5 Nov 2012 19:53:52 +0000
> From: Oscar Benjamin <[email protected]>
> Subject: [Haskell-beginners] Missing termination rule for recursive
> function
> To: [email protected]
> Message-ID:
> <CAHVvXxQK+Ex96r3nDGw9RQr3hzp8FRKjm+ntar17Fq70q=qj=a...@mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Hi all,
>
> I'm new to this list and I'm in the very early stages of learning
> Haskell but I am confident with Python and some other languages.
> Seeing the connection between Haskell's lists and Python's generators
> I tried to reimplement a generator-based Python program in Haskell. I
> now have it working but I was hoping that someone could help me
> resolve a few queries.
>
> The Python program used itertools.permutations which is an iterator
> that yields all permutations of a sequence. Does Haskell have a
> similar function in it's standard library?
>
> I found a suggestion [1] for implementing a permutations function:
>
> -- Select each item and remainder from a sequence
> selections :: [a] -> [(a, [a])]
> selections [] = []
> selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
>
> -- Permutations of a sequence
> permutations :: [a] -> [[a]]
> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations
> ys ]
>
> After a while I established that this permutations function seemed to
> be returning an empty list. Looking at it I thought that it might be
> missing a termination condition so I added
>
> permutations [] = []
>
> but the result was unchanged. When I changed it to
>
> permutations [] = [[]]
>
> I got the desired result. I can understand why this termination
> condition is needed to make the function recurse properly.
>
> What's confusing me though is why neither of the first two raised any
> kind of error at compile- or run-time. I would understand if an
> infinite loop had occurred (a common result for non-terminating
> recursion) but as far as I can tell it just returned an empty list.
> Can anyone explain to me how the function terminates in the three
> different cases?
>
> Also what is a good way of debugging this kind of problem? I found it
> quite difficult to establish that permutations was returning an empty
> list (in context there were other functions that could have been
> failing).
>
>
> Thanks in advance,
> Oscar
>
> [1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html
>
>
>
> ------------------------------
>
> Message: 7
> Date: Mon, 05 Nov 2012 22:00:22 +0100
> From: Daniel Fischer <[email protected]>
> Subject: Re: [Haskell-beginners] Missing termination rule for
> recursive function
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: text/plain; charset="us-ascii"
>
> On Montag, 5. November 2012, 19:53:52, Oscar Benjamin wrote:
>> Hi all,
>>
>> I'm new to this list
>
> Welcome, then.
>
>> The Python program used itertools.permutations which is an iterator
>> that yields all permutations of a sequence. Does Haskell have a
>> similar function in it's standard library?
>
> There's permutations in Data.List
>
> Prelude Data.List> permutations [1,2,3]
> [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
>
> which even works on infinite lists:
>
> Prelude Data.List> map (take 5) . take 5 $ permutations [1 .. ]
> [[1,2,3,4,5],[2,1,3,4,5],[3,2,1,4,5],[2,3,1,4,5],[3,1,2,4,5]]
>
> (as a consequence, it is a bit slower than an optimal implementation
> working
> only on finite lists could be).
>
>>
>> I found a suggestion [1] for implementing a permutations function:
>>
>> -- Select each item and remainder from a sequence
>> selections :: [a] -> [(a, [a])]
>> selections [] = []
>> selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
>>
>> -- Permutations of a sequence
>> permutations :: [a] -> [[a]]
>> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations
>> ys ]
>>
>> After a while I established that this permutations function seemed to
>> be returning an empty list. Looking at it I thought that it might be
>> missing a termination condition so I added
>>
>> permutations [] = []
>>
>> but the result was unchanged.
>
> permutations [x] = [ y:zs | (y,ys) <- selections [x], zs <- permutations
> ys]
> ~> [ y:zs | (y,ys) <- [(x,[])], zs <- permutations ys]
> ~> [ x:zs | zs <- permutations []]
> ~> []
>
> since permutations [] = []
>
>> When I changed it to
>>
>> permutations [] = [[]]
>
> That changes the last steps above to
>
> ~> [ x:zs | zs <- permutations []]
> ~> [ x:zs | zs <- [[]] ]
> ~> [ x:[] ]
> ~> [ [x] ]
>
> and the former is not even correct, because there is exactly one
> permutation
> of an empty list.
>
>>
>> I got the desired result. I can understand why this termination
>> condition is needed to make the function recurse properly.
>>
>> What's confusing me though is why neither of the first two raised any
>> kind of error at compile- or run-time.
>
> The type is still correct, the empty list can have elements of any type,
>
> [] :: [a]
>
> in particular, the elements can be lists, in which case the type is
> specialised to
>
> [] :: [[b]]
>
> So the compiler has no reason to complain.
>
> And at runtime, you're only `concatMap`ping over an empty list, resulting
> in
> an empty list, that's normal and nothing that could cause an exception.
>
>> I would understand if an
>> infinite loop had occurred (a common result for non-terminating
>> recursion) but as far as I can tell it just returned an empty list.
>> Can anyone explain to me how the function terminates in the three
>> different cases?
>
> We had two cases above, the one without explicit base case remains
>
>> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations
>> ys ]
>
> That leads to
>
> permutations [] = [ y:zs | (y,ys) <- selections [], zs <- permutations
> ys ]
> ~> [ y:zs | (y,ys) <- [], zs <- permutations ys ]
>
> and you're again `concatMap`ping over an empty list, resulting in an empty
> list. If you're starting with a non-empty finite list, the recursive call
> is
> to a list one element shorter etc. until finally
>
> permutations []
>
> is called - and then you prepend an element ot each list in an empty list,
> resulting in an empty list...
>
>>
>> Also what is a good way of debugging this kind of problem? I found it
>> quite difficult to establish that permutations was returning an empty
>> list (in context there were other functions that could have been
>> failing).
>>
>
> Trace the execution of very simple cases (empty lists, singleton lists,
> lists
> with two elements) by hand with pencil and paper. That's the most
> instructive
> and fruitful way.
>
> Check the results of simple cases against what you know the result ought
> to
> be.
>
> Single-step through the evaluation of simple cases in the ghci debugger if
> necessary.
>
>
>
> ------------------------------
>
> Message: 8
> Date: Mon, 5 Nov 2012 16:27:47 -0500 (EST)
> From: Jay Sulzberger <[email protected]>
> Subject: Re: [Haskell-beginners] Missing termination rule for
> recursive function
> To: [email protected]
> Message-ID: <[email protected]>
> Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
>
>
>
> On Mon, 5 Nov 2012, Oscar Benjamin <[email protected]> wrote:
>
>> Hi all,
>>
>> I'm new to this list and I'm in the very early stages of learning
>> Haskell but I am confident with Python and some other languages.
>> Seeing the connection between Haskell's lists and Python's generators
>> I tried to reimplement a generator-based Python program in Haskell. I
>> now have it working but I was hoping that someone could help me
>> resolve a few queries.
>>
>> The Python program used itertools.permutations which is an iterator
>> that yields all permutations of a sequence. Does Haskell have a
>> similar function in it's standard library?
>>
>> I found a suggestion [1] for implementing a permutations function:
>>
>> -- Select each item and remainder from a sequence
>> selections :: [a] -> [(a, [a])]
>> selections [] = []
>> selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
>>
>> -- Permutations of a sequence
>> permutations :: [a] -> [[a]]
>> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations
>> ys ]
>>
>> After a while I established that this permutations function seemed to
>> be returning an empty list. Looking at it I thought that it might be
>> missing a termination condition so I added
>>
>> permutations [] = []
>>
>> but the result was unchanged. When I changed it to
>>
>> permutations [] = [[]]
>>
>> I got the desired result. I can understand why this termination
>> condition is needed to make the function recurse properly.
>>
>> What's confusing me though is why neither of the first two raised any
>> kind of error at compile- or run-time. I would understand if an
>> infinite loop had occurred (a common result for non-terminating
>> recursion) but as far as I can tell it just returned an empty list.
>> Can anyone explain to me how the function terminates in the three
>> different cases?
>
> Let us assume we are in case 0:
>
> We have neither
>
> permutations [] = []
>
> nor
>
> permutations [] = [[]]
>
> in our code.
>
> Then let us calculate
>
> permutations ["a"]
>
> Assuming selections is correct, we have
>
> permutations ["a"] ~> the list of all lists of form "a":(something that
> lies in permutations [])
>
> So what is the value of permutations []? It is the list of all things of
> form
>
> y:zs
>
> such that
>
> (y,ys) lies in selections xs and zs lies in permutations ys
>
> where xs = []. But there are no such things. And so the list of
> sll such things is the empty list [].
>
> What is perhaps confusing is that, at this juncture, one tends to
> think that
>
> y:zs
>
> must really be
>
> y:[]
>
> but it is not. [] is an object in the Haskell world, and a
> subexpression zs appears in the expression on the right hand side
> of
>
> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations
> ys ]
>
> but there is no object in the Haskell world which can be the
> value of zs because there is no object which can be the value of
> (y, ys), because the line
>
> selections [] = []
>
> appears in the definition of selections: (y, ys) would have to be
> an element, that is an object lying in, selections [], but
> selections [] = [].
>
>>
>> Also what is a good way of debugging this kind of problem? I found it
>> quite difficult to establish that permutations was returning an empty
>> list (in context there were other functions that could have been
>> failing).
>>
>>
>> Thanks in advance,
>> Oscar
>
> I am not sure. I think many people just slowly "by hand" run
> their own interpreter in their head.
>
> ad types: I conjecture that Haskell's type checker, by design,
> when run on this code, treats the expressions [] and [["a"]] as
> both being of type [[a]].
>
> If my conjecture is correct, then case 0 code would pass the type
> checker.
>
> ad termination: the "list comprehension" operator returns,
> correctly according to the conventions of the twentieth century,
> the null list when there are no objects which satisfy the
> conditions written to the right of the "|".
>
> oo--JS.
>
>
>>
>> [1] http://www.haskell.org/pipermail/haskell-cafe/2002-June/003122.html
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
>
>
>
>
> ------------------------------
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
> End of Beginners Digest, Vol 53, Issue 7
> ****************************************
>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 53, Issue 9
****************************************
