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. Finite self-referential list hangs. (tcollin371)
2. Re: Finite self-referential list hangs. (Dean Herington)
3. Re: Finite self-referential list hangs. (Brent Yorgey)
4. Re: Finite self-referential list hangs (tcollin371)
5. Re: gui pkgs (Yawar Amin)
6. When a return type constrained by class (Haisheng Wu)
7. Re: When a return type constrained by class (Brandon Allbery)
8. Re: When a return type constrained by class (Kyle Murphy)
----------------------------------------------------------------------
Message: 1
Date: Sat, 17 Mar 2012 17:32:24 +0000 (GMT+00:00)
From: tcollin371 <[email protected]>
Subject: [Haskell-beginners] Finite self-referential list hangs.
To: [email protected]
Message-ID:
<28078234.1332005544917.javamail.r...@mswamui-valley.atl.sa.earthlink.net>
Content-Type: text/plain; charset=UTF-8
I am trying to generate a search tree for a logic puzzle using a list that
generates itself by using earlier states to derive later states. The search
tree is finite, but when it reaches the end, it hangs and while the list
doesn't grow, it doesn't finish.
I've boiled the problem down to a much simpler list as follows:
tryThis :: [Int]
tryThis = 3 : [ x | x <- tryThis' tryThis]
where
tryThis' :: [Int] -> [Int]
tryThis' [] = []
tryThis' (x : xs) = result' x ++ tryThis' xs
where
result' :: Int -> [Int]
result' 3 = [2, 2, 2]
result' 2 = [1, 1]
result' 1 = [0]
result' 0 = []
When I load this into GHCi and type tryThis, it prints a list of all of the
numbers I would expect, then hangs. Does the self-generating technique not
work with finite lists? Shouldn't tryThis' just generate a final empty list
that would terminate this? How can this be written to successfully terminate?
Thank you for any help.
-TC
------------------------------
Message: 2
Date: Sat, 17 Mar 2012 15:18:38 -0400
From: Dean Herington <[email protected]>
Subject: Re: [Haskell-beginners] Finite self-referential list hangs.
To: tcollin371 <[email protected]>, [email protected]
Message-ID: <a06240800cb8a925db1a5@[10.0.1.7]>
Content-Type: text/plain; charset="us-ascii" ; format="flowed"
At 5:32 PM +0000 3/17/12, tcollin371 wrote:
>I am trying to generate a search tree for a logic puzzle using a
>list that generates itself by using earlier states to derive later
>states. The search tree is finite, but when it reaches the end, it
>hangs and while the list doesn't grow, it doesn't finish.
>
>I've boiled the problem down to a much simpler list as follows:
>
>tryThis :: [Int]
>tryThis = 3 : [ x | x <- tryThis' tryThis]
> where
> tryThis' :: [Int] -> [Int]
> tryThis' [] = []
> tryThis' (x : xs) = result' x ++ tryThis' xs
> where
> result' :: Int -> [Int]
> result' 3 = [2, 2, 2]
> result' 2 = [1, 1]
> result' 1 = [0]
> result' 0 = []
>
>When I load this into GHCi and type tryThis, it prints a list of all
>of the numbers I would expect, then hangs. Does the self-generating
>technique not work with finite lists? Shouldn't tryThis' just
>generate a final empty list that would terminate this? How can this
>be written to successfully terminate?
As you observed, tryThis' doesn't know to terminate because its xs
never becomes [], even at (what you know is) the end. You need to
program a termination check that doesn't need to look into the
future. Here's one way (probably not the best):
tryThis2 :: [Int]
tryThis2 = 3 : [ x | x <- tryThis' 1 0 tryThis2]
where
tryThis' :: Int -> Int -> [Int] -> [Int]
tryThis' n m _ | m == n = []
tryThis' n m (x : xs) = let gen = result' x in gen ++ tryThis' (n
+ length gen) (m + 1) xs
where
result' :: Int -> [Int]
result' 3 = [2, 2, 2]
result' 2 = [1, 1]
result' 1 = [0]
result' 0 = []
------------------------------
Message: 3
Date: Sat, 17 Mar 2012 16:26:25 -0400
From: Brent Yorgey <[email protected]>
Subject: Re: [Haskell-beginners] Finite self-referential list hangs.
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Mar 17, 2012 at 05:32:24PM +0000, tcollin371 wrote:
> I am trying to generate a search tree for a logic puzzle using a list that
> generates itself by using earlier states to derive later states. The search
> tree is finite, but when it reaches the end, it hangs and while the list
> doesn't grow, it doesn't finish.
>
> I've boiled the problem down to a much simpler list as follows:
>
> tryThis :: [Int]
> tryThis = 3 : [ x | x <- tryThis' tryThis]
> where
> tryThis' :: [Int] -> [Int]
> tryThis' [] = []
> tryThis' (x : xs) = result' x ++ tryThis' xs
> where
> result' :: Int -> [Int]
> result' 3 = [2, 2, 2]
> result' 2 = [1, 1]
> result' 1 = [0]
> result' 0 = []
By the way,
[ x | x <- foo ] == foo
so we can simplify this to
tryThis = 3 : tryThis' tryThis
where
...
Also, tryThis' = concatMap result', so it can be further simplified to
tryThis = 3 : concatMap result' tryThis
where
result' :: Int -> [Int]
result' 3 = ...
Of course, this still does not terminate. The problem, intuitively,
is that the concatMap "catches up with itself" and after the last 0 is
generated, it is waiting to find out what the next element will be,
in order to generate the very element it is waiting for! Here is one
way to solve it:
tryThis2 :: [Int]
tryThis2 = concat tryThis2'
where
tryThis2' = [3] : process tryThis2'
process ([] : _) = []
process (xs : xss) = concatMap result' xs : process xss
result' 3 = [2,2,2]
result' 2 = [1,1]
result' 1 = [0]
result' 0 = []
The idea is that we delay doing the concat until the very end, so
during the actual generation we have a list of lists, where each inner
list contains all the numbers generated at some "stage". For example
we have [[3], [2,2,2], ...]. That way we can tell when no new numbers
were generated by the previous stage and stop (that's the first case
of 'process').
-Brent
------------------------------
Message: 4
Date: Sat, 17 Mar 2012 23:46:54 +0000 (GMT+00:00)
From: tcollin371 <[email protected]>
Subject: Re: [Haskell-beginners] Finite self-referential list hangs
To: Hask <[email protected]>
Message-ID:
<27835162.1332028014689.javamail.r...@mswamui-valley.atl.sa.earthlink.net>
Content-Type: text/plain; charset="us-ascii"
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120317/d638ec86/attachment-0001.htm>
------------------------------
Message: 5
Date: Sun, 18 Mar 2012 02:11:50 +0000 (UTC)
From: Yawar Amin <[email protected]>
Subject: Re: [Haskell-beginners] gui pkgs
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi Andy,
Andy <ablaroc <at> gmail.com> writes:
> [...]
> Also, is there a better toolkit for doing guis than wxHaskell? I
> tried Glade, but it's so bug-ridden I couldn't get anything done. I need
> help.
If you're OK with just doing some GUI programming, and don't mind if
it's not wxHaskell, try out HTk (
http://www.informatik.uni-bremen.de/htk/ ). It's outdated, but it's
quick and easy to set up with Cabal and it works. I even did a very
simple reverse-polish notation calculator using it (
https://github.com/yawaramin/HTkalc/blob/master/HTkalc.hs ).
Although mine has a pretty serious bug--it only takes single-digit
numbers as input right now. Still, it should give you a feel for the toolkit
if you're interested.
Regards,
Yawar
------------------------------
Message: 6
Date: Sun, 18 Mar 2012 14:23:20 +0800
From: Haisheng Wu <[email protected]>
Subject: [Haskell-beginners] When a return type constrained by class
To: Haskell Beginer <[email protected]>
Message-ID:
<cafj8lzcdbm-ha_q-znht_f4yy-ob1o-jmytsvcfmmptuukv...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Hi there,
Do you have any idea why the following code is not valid?
class Guess g where
makeGuess :: g -> String
instance Guess GuessLetter where
makeGuess = ...
instance Guess GuessWord where
makeGuess = ...
*-- | This function is nod valid *
nextGuess :: Guess g => String -> g
nextGuess = ...
Thank you.
-Haisheng
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120318/f1ec5771/attachment-0001.htm>
------------------------------
Message: 7
Date: Sun, 18 Mar 2012 05:00:46 -0400
From: Brandon Allbery <[email protected]>
Subject: Re: [Haskell-beginners] When a return type constrained by
class
To: Haisheng Wu <[email protected]>
Cc: Haskell Beginer <[email protected]>
Message-ID:
<CAKFCL4X5OrYiXq67jU4uVwqYd==kvvyju9habet3ctbfphe...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sun, Mar 18, 2012 at 02:23, Haisheng Wu <[email protected]> wrote:
> Hi there,
> Do you have any idea why the following code is not valid?
>
> class Guess g where
> makeGuess :: g -> String
>
> instance Guess GuessLetter where
> makeGuess = ...
>
> instance Guess GuessWord where
> makeGuess = ...
>
> *-- | This function is nod valid *
> nextGuess :: Guess g => String -> g
> nextGuess = ...
>
You are probably assuming that you get to decide within nextGuess what type
it will return; in fact, the type it will return is set by its context when
invoked, and your implementation must be prepared to return any Guess based
on what the caller wants. Since nextGuess has no way to *get* at that
context, and the typeclass has no method that can be used to produce a
result based on the requested result type (as with e.g. Read), it's not
clear to me that it can actually return anything (that is, the only
possible result is _|_).
Mantra: "Typeclasses are not OOP." Don't try to think of them as OOP, you
will only get into trouble.
--
brandon s allbery [email protected]
wandering unix systems administrator (available) (412) 475-9364 vm/sms
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120318/e4474e5d/attachment-0001.htm>
------------------------------
Message: 8
Date: Sun, 18 Mar 2012 05:13:10 -0400
From: Kyle Murphy <[email protected]>
Subject: Re: [Haskell-beginners] When a return type constrained by
class
To: Haisheng Wu <[email protected]>
Cc: Haskell Beginer <[email protected]>
Message-ID:
<ca+y6jcyjk4g512x-tml5tjabjz885odzikharnsojtuckqs...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I'd guess the problem is because nextGuess isn't capable of producing any
instance of Guess. The type signature of a function isn't just to provide
callers information about a function like in most languages, it's also a
contract the function itself must abide by. In contrast it's common in an
OO language like Java to provide a more general return type like an
interface or superclass in the method declaration, and then to return a
more concrete type in the actual method. Haskell in contrast requires that
you be capable of returning *anything* that your functions type signature
claims it can. In your example, nextGuess must be capable of producing
*any* instance of nextGuess that a caller of the function requests. Put
another way, both of these must be valid:
nextGuess "example" :: GuessLetter
nextGuess "example" :: GuessWord
Typically this is accomplished by making a function like nextGuess part of
the class as in how Read does it:
class Read a where
read :: Read a => String -> a
By definition then, any instance of read must provide a read function
capable of producing something of that type. So, it seems obvious the
solution to your problem is to make nextGuess part of the Guess class.
Alternatively if that's not really what you're trying to accomplish the
type signature of nextGuess is probably wrong. If you provide more detail
on what you're attempting to do maybe someone on here can suggest another
way of accomplishing it.
-R. Kyle Murphy
--
Curiosity was framed, Ignorance killed the cat.
On Sun, Mar 18, 2012 at 02:23, Haisheng Wu <[email protected]> wrote:
> Hi there,
> Do you have any idea why the following code is not valid?
>
> class Guess g where
> makeGuess :: g -> String
>
> instance Guess GuessLetter where
> makeGuess = ...
>
> instance Guess GuessWord where
> makeGuess = ...
>
> *-- | This function is nod valid *
> nextGuess :: Guess g => String -> g
> nextGuess = ...
>
>
> Thank you.
>
> -Haisheng
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120318/0b72f7ec/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 45, Issue 22
*****************************************
