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. Re: [Haskell-cafe] What is an "expected type" ...
(Brandon S. Allbery KF8NH)
2. Re: [Haskell-cafe] What is an "expected type" ...
(Daniel Fischer)
3. Re: High precision doubles (Matthew Eastman)
4. Rigid type variables match error (Darryn)
5. Re: [Haskell-cafe] What is an "expected type" ... (michael rice)
----------------------------------------------------------------------
Message: 1
Date: Sun, 28 Jun 2009 12:06:52 -0400
From: "Brandon S. Allbery KF8NH" <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] What is an "expected
type" ...
To: michael rice <[email protected]>
Cc: [email protected], Haskell Cafe mailing list
<[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Skipped content of type multipart/alternative-------------- next part
--------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part
Url :
http://www.haskell.org/pipermail/beginners/attachments/20090628/112a0bb5/PGP-0001.bin
------------------------------
Message: 2
Date: Sun, 28 Jun 2009 18:52:32 +0200
From: Daniel Fischer <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] What is an "expected
type" ...
To: [email protected]
Cc: [email protected], michael rice <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-15"
Am Sonntag 28 Juni 2009 18:06:52 schrieb Brandon S. Allbery KF8NH:
> On Jun 28, 2009, at 12:02 , michael rice wrote:
> > dec2bin :: Integer -> [Integer]
> > dec2bin n = dec2bin' n []
> > where dec2bin' n acc
> >
> > | n == 0 = acc
> > | otherwise = let r = rem n 2
> >
> > m = div (n - r) 2
> > in dec2bin' m (r : acc)
> >
> > is there any way to assign a type signature to the helper function?
>
> Same way you do for a top level binding:
> >> dec2bin :: Integer -> [Integer]
> >> dec2bin n = dec2bin' n []
> >> where dec2bin' :: Integer -> [Integer] -> [Integer]
> >> dec2bin' n acc
> >>
> >> | n == 0 = acc
> >> | otherwise = let r = rem n 2
> >>
> >> m = div (n - r) 2
> >> in dec2bin' m (r : acc)
But, to mention it before it bites, putting type signatures involving type
variables on
local helper functions is not entirely straightforward. Consider
inBase :: Integral a => a -> a -> [a]
0 `inBase` b = [0]
n `inBase` b = local n []
where
local 0 acc = acc
local m acc = case m `divMod` b of
(q,r) -> local q (r:acc)
Now try giving a type signature to local. You can't.
What is the type of local?
It's (type of b) -> [type of b] -> [type of b],
but "type of b" isn't available.
If you try
local :: a -> [a] -> [a]
or
local :: Integral a => a -> [a] -> [a],
you are saying that local works for *every* type a (or for every type a which
is an
instance of Integral), because the 'a' from local's type signature is a new
(implicitly
forall'd) type variable.
To be able to give local a type signature, you must bring the type variable 'a'
into
scope:
{-# LANGUAGE ScopedTypeVariables #-}
inBase :: forall a. Integral a => a -> a -> [a]
0 `inBase` b = [0]
n `inBase` b = local n []
where
local :: a -> [a] -> [a] -- now this a is the same a as the one above
local 0 acc = acc
local m acc = case m `divMod` b of
(q,r) -> local q (r:acc)
------------------------------
Message: 3
Date: Sun, 28 Jun 2009 22:34:51 -0400
From: Matthew Eastman <[email protected]>
Subject: Re: [Haskell-beginners] High precision doubles
To: Aaron MacDonald <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
This is a coincidence. I just finished writing a hexagonal (and
square) maze generator.
I used Wilson's algorithm, which builds a spanning tree by performing
a random walk from each cell not in the maze until it reaches a cell
that is in the maze. It then adds the path and goes at it again until
every cell is in the maze.
If you're using a grid, even one without bounds, it makes sense to use
integer coordinates and map them to floating point when you need to,
like some others have suggested.
The grid I used looked something like this:
___ ___
___/ \___/ \___
/ \___/ \___/ \
\___/2,2\___/ \___/
/1,2\___/3,2\___/ \
\___/2,1\___/ \___/
/1,1\___/3,1\___/ \
\___/ \___/ \___/
It would work with negative numbers as well, if you need the grid to
be able to expand in every direction.
You move north, south, east, or west by adding to or subtracting from
the x and y co-ordinates.
If the x coordinate is even, you add 1 to y when you move north-east
or north-west.
If the x coordinate is odd, you subtract 1 from y when you move south-
east or south-west.
Then when you're testing whether a cell is in your maze you just need
to check the (x,y) integer pair and not have to worry about floating
point precision, and you can get all the cells adjacent to a specific
cell by adding to and subtracting from the x or y value of a cell.
I found it easier to keep track of which walls each cell has instead
of which cells it's adjacent to, but either one works.
Just for fun, one of the mazes it made:
___ ___ ___ ___ ___
___/ \___/ \___/ \___/ \___/ \___
/ \ \ / / / \ \
\ \___/ ___/ ___/ / \ /
/ \___/ ___ \ \___/ \ / \
\ / \___/ \ / \ / \___ \ /
/ / ___/ \___/ ___ \___/ \
\___/ / \___ \___/ \___ \ /
/ \ / ___ ___/ \___/ \
\___ \___/ \ \ / ___/
/ ___ \___/ \___/ \___/ \___ \
\___/ \___/ \___/ \___/ \___/ \___/
On 24-Jun-09, at 10:10 PM, Aaron MacDonald wrote:
>
> On 24-Jun-09, at 10:18 PM, Andrew Hunter wrote:
>> More to the point, however: you don't want more precision. Welcome
>> to
>> the world of numerical algorithms; floating point arithmetic is
>> inherently inexact. Get used to it. For example, I'll bet your
>> errors are caused by testing for equality against zero, and if I had
>> to guess, you're probably trying to terminate a procedure when some
>> value hits zero? It's not going to; you need to introduce the
>> concept
>> of tolerances, and accept if |val| < tol. This is a simplistic
>> solution and not really right in most cases, but might help. If you
>> want more advice about how to handle floating-point inaccuracy, could
>> you provide a program and what's going wrong?
>
> What I'm specifically working on is a maze generator. The generator
> is based on Prim's algorithm: starting with a graph containing a
> single node, I connect new nodes to existing nodes that are not
> surrounded yet until I've reached a specified number of nodes in the
> graph.
>
> In my case, the maze is on a hexagonal grid. There are no
> boundaries around the maze, so the generator may attach hexagonal
> cells, or nodes, from any side (I don't particularly care if the
> generator sometimes makes one long hallway). Each hexagonal cell is
> represented in the graph as a co-ordinate representing the cell's
> centre. I have a function that takes a co-ordinate and returns a
> list of co-ordinates representing the centres of the adjacent cells.
> Keeping track of the hexagons' positions is important because these
> mazes will be levels for a game I hope to somehow put together; the
> potions would be used for drawing the maze and for AI pathfinding.
>
> When adding a new node/hex to the graph/maze, I pick an existing
> node and get all of its neighbour co-ordinates, filtering out co-
> ordinates that represent nodes already present in the graph. The
> problem is that, due to floating point errors, these co-ordinates
> are not be exact. If hex A has the co-ordinate for hex B in its list
> of adjacent hexes, hex B would not necessarily have the co-ordinate
> for hex A in its own list. Things get mismatched quickly.
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 4
Date: Sat, 27 Jun 2009 10:18:02 +0930
From: Darryn <[email protected]>
Subject: [Haskell-beginners] Rigid type variables match error
To: [email protected]
Message-ID: <1246063682.7752.8.ca...@epicurus>
Content-Type: text/plain
Hi, I wonder if anyone can explain what is going on here and what to do
about it. I'm fairly new to Haskell, so apologies in advance if my
question seems naive. I've cut my code down to a minimum that reproduces
the problem. I receive an error in GHCI in the following code,
complaining that it cannot match the rigid type variables for the
instance definition for Ainst for the function a3. Can anyone advise
about what to do about it?
------------------------------------------------
class A a where
a1 :: a
a2 :: a -> a
a3 :: (B b) => b -> a
class B b where
b1 :: Int -> b
data (B b) => Ainst b = I | J (Ainst b) | K b
instance (B b) => A (Ainst b) where
a1 = I
-- a2 :: (B b, A a) => a -> a
a2 = J
-- a3 :: (B b, A a) => b -> a
a3 = K -- Error!
-- a3 = K `asTypeOf` a3 -- Error even with this!
data Binst = Val Int
instance B Binst where
b1 = Val
------------------------------------------------
Test5.hs:17:9:
Couldn't match expected type `b1' against inferred type `b'
`b1' is a rigid type variable bound by
the instance declaration at Test5.hs:12:12
`b' is a rigid type variable bound by
the type signature for `a3' at Test5.hs:5:13
Expected type: b -> Ainst b1
Inferred type: b -> Ainst b
In the expression: K `asTypeOf` a3
In the definition of `a3': a3 = K `asTypeOf` a3
Failed, modules loaded: none.
------------------------------
Message: 5
Date: Sun, 28 Jun 2009 09:02:29 -0700 (PDT)
From: michael rice <[email protected]>
Subject: [Haskell-beginners] Re: [Haskell-cafe] What is an "expected
type" ...
To: Joe Fredette <[email protected]>
Cc: [email protected], Haskell Cafe mailing list
<[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hey Joe, all,
Got it. Thanks!
An associated question: In programming a local "helper" or "auxilliary"
function such as dec2bin' in
dec2bin :: Integer -> [Integer]
dec2bin n = dec2bin' n []
where dec2bin' n acc
| n == 0 = acc
| otherwise = let r = rem n 2
m = div (n - r) 2
in dec2bin' m (r : acc)
is there any way to assign a type signature to the helper function?
Michael
--- On Sun, 6/28/09, Joe Fredette <[email protected]> wrote:
From: Joe Fredette <[email protected]>
Subject: Re: [Haskell-cafe] What is an "expected type" ...
To: "michael rice" <[email protected]>
Cc: "Haskell Cafe mailing list" <[email protected]>,
[email protected]
Date: Sunday, June 28, 2009, 11:29 AM
When Haskell runs it's type checker, it tries to "guess" the type of each
function. Thats why you can write:
map (+1)
and it knows that you're talking about a function of type:
Num a => [a] -> [a]
Another thing, called 'defaulting' resolves this, but you didn't ask about
that, so I won't go into it.
An expected type is one that you provide to the compiler in the form of a type
signature, this can be used to specialize a general type (like the one I
showed) or
to resolve ambiguous types the compiler can't, or just for documentation/good
practice. So when I write:
foo :: Num a => [a] -> [a]
foo ls = map (+1) ls
The "expected type" for `foo` is `Num a => [a] -> [a]`. I imagine you're asking
this because you got an error which said your expected type doesn't match your
inferred type. That might, for instance, happen if I wrote:
bar :: String
bar = 'a'
'a' has type `Char`, since `String` is not `Char`, the type checker infers that
'a' has type char, but _expects_ it to be type String. Two solutions are as
follows:
--- Method 1
bar :: Char
bar = 'a'
--- Method 2
bar :: String
bar = "a"
Can you see why those two changes fix the problem?
Also, just as a matter of process, I forwarded this to the haskell-beginners
list, as I imagine type errors like these come up a lot, and someone probably
has a better explanation over there.
/Joe
michael rice wrote:
> as opposed to an "inferred type"?
>
> Michael
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Haskell-Cafe mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090628/28ff14de/attachment.html
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 12, Issue 15
*****************************************
