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
****************************************
