Types and hashes of hashes, trouble for a Java-programmer...

newer
The Monad.Reader (14) - Call for...

John Smith

13 Apr 2009 13 Apr '09

11:42 a.m.

Hi, a java-programmer running into trouble while trying to learn Haskell. I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed? My attempt: removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key) test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 maybeOuterHash <- HashTable.lookup h 3 res <- removeMaybe (removeMaybeHash maybeOuterHash) 1000 return res Any clues? In java this would be as simple as (pseudocode): h.lookup(3).lookup(1000) Cheers, Pedro

Attachments:

attachment.html (text/html — 921 bytes)

Show replies by date

John A. De Goes

13 Apr 13 Apr

12:02 p.m.

Why not use an ordered pair as the key? Regards, John A. De Goes N-BRAIN, Inc. The Evolution of Collaboration http://www.n-brain.net | 877-376-2724 x 101 On Apr 13, 2009, at 9:42 AM, John Smith wrote:

...

Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 maybeOuterHash <- HashTable.lookup h 3 res <- removeMaybe (removeMaybeHash maybeOuterHash) 1000 return res

Any clues?

In java this would be as simple as (pseudocode): h.lookup(3).lookup(1000)

Cheers,

Pedro

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

John Smith

12:27 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

If you mean using a non-destructive map where the IO-problem is absent, that is a doable thing. But it would be like cheating :-) What I try do do is something like: test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 res <- case HashTable.lookup h 3 of Nothing -> Nothing Just outer -> HashTable.lookup outer 1000 return res

John Van Enk

12:30 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

...

But it would be like cheating :-)

In this case, the IO method *is* cheating. /jve On Mon, Apr 13, 2009 at 12:27 PM, John Smith wrote:

...

If you mean using a non-destructive map where the IO-problem is absent, that is a doable thing. But it would be like cheating :-)

What I try do do is something like:

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 res <- case HashTable.lookup h 3 of Nothing -> Nothing Just outer -> HashTable.lookup outer 1000 return res _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- /jve

John Smith

12:33 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Yes, I see what you mean. But still wan't to know if it is possible :-)

Lennart Augustsson

12:50 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

No, removing IO is the right way. There is no reason to involve IO for this. -- Lennart On Mon, Apr 13, 2009 at 6:27 PM, John Smith wrote:

...

If you mean using a non-destructive map where the IO-problem is absent, that is a doable thing. But it would be like cheating :-)

What I try do do is something like:

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 res <- case HashTable.lookup h 3 of Nothing -> Nothing Just outer -> HashTable.lookup outer 1000 return res _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

John Smith

12:53 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Yes, got the point. But is it not possible to "wrap IO inside IO" at all? What would the program look like, just for the exercise? On Mon, Apr 13, 2009 at 6:50 PM, Lennart Augustsson wrote:

...

No, removing IO is the right way. There is no reason to involve IO for this.

-- Lennart

On Mon, Apr 13, 2009 at 6:27 PM, John Smith wrote:

...
If you mean using a non-destructive map where the IO-problem is absent, that is a doable thing. But it would be like cheating :-)

What I try do do is something like:

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 res <- case HashTable.lookup h 3 of Nothing -> Nothing Just outer -> HashTable.lookup outer 1000 return res _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Achim Schneider

12:33 p.m.

"John A. De Goes" wrote:

...

Why not use an ordered pair as the key?

Well, that might be seriously less efficient, depending on the type and size of keys: By nesting, you might avoid computing the hash of a two-megabyte key in case the outer lookup failed. The same goes for any other Map implementation, of course, O(zarroo) is always faster than anything. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

John Smith

12:49 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Yes, I see. Good points in both answers, but I still would like to see how to do it with the mutable hash, if possible...

Achim Schneider

1:49 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

John Smith wrote:

...

Yes, I see. Good points in both answers, but I still would like to see how to do it with the mutable hash, if possible...

test = do h <- H.new (==) id h1 <- H.new (==) id H.insert h 3 h1 H.insert h1 1 1000 inner <- H.lookup h 3 case inner of Nothing -> return Nothing Just outer -> H.lookup outer 1000 you forgot to lift the Nothing into the IO monad. I like this one: lookup' :: key -> b -> HashTable key (HashTable b val) -> IO (Maybe val) lookup' k l h = H.lookup h k >>= maybe (return Nothing) ((flip H.lookup) l) test' = do h <- H.new (==) id h1 <- H.new (==) id H.insert h 3 h1 H.insert h1 1 1000 lookup' 3 1000 h -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Achim Schneider

12:25 p.m.

John Smith wrote:

...

Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 maybeOuterHash <- HashTable.lookup h 3 res <- removeMaybe (removeMaybeHash maybeOuterHash) 1000 return res

Any clues?

Just don't use it, someone deserves to be disemboweled for implementing it via IO. Most likely, you don't want to have a hash in specific, but a key->value mapping in general, and the Haskell libs offer more than one algorithm to do that, the most basic one being Data.Map, and the rest having more or less the same interface (e.g. IntMap, or Trie). There are two possibilities to "nest" two maps: The first being indexing the map by a tuple of both lookup keys, the second one using two maps, one inside the other. Personally, I always use Data.Map unless I identify it as a bottleneck after completing the program. Using tuples should be straight forward, if you want to nest Maps, you will want to chain two lookup's together. The most straight-forward way to do this is using Maybe's monad instance, which looks like this: instance Monad Maybe where (Just x) >>= k = k x Nothing >>= _ = Nothing It "bypasses" the second argument of >>= in case the first argument is Nothing. Filling in the types, we get (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b . "a" is going to be the inner map, which the second lookup will take as second parameter, so you can write this: import Data.Map as M lookup' :: (Ord k, Ord l) => Map k (Map l v) -> k -> l -> Maybe v lookup' m k l = M.lookup k m >>= M.lookup l ...Somewhere, I once read that monads can be seen as some fancy way to do OOP's foo.bar().baz(), but I'm not supposed to tell you that: You should try your best to forget anything you know about programming if you come from an imperative language and want to learn haskell :) -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

Jason Dagit

12:55 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Others have provided help to answer your question but I'd like to provide a little bit different feedback. On Mon, Apr 13, 2009 at 8:42 AM, John Smith wrote:

...

Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

When you see yourself writing a function like this, you could write it like this instead: removeMaybeHash (Just ref) = ref removeMaybeHash Nothing = HashTable.new (==) (\key -> key) Hopefully you agree this 2 line version is more clear. You could go further of course and use the function 'maybe' from the prelude, and pass the function 'id' instead of \key -> key, but I don't want to overwhelm you. Good luck, Jason

John Smith

12:59 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Yes, agreed. Got any clue on the original problem (except to use Data.Map)? On Mon, Apr 13, 2009 at 6:55 PM, Jason Dagit wrote:

...

Others have provided help to answer your question but I'd like to provide a little bit different feedback.

On Mon, Apr 13, 2009 at 8:42 AM, John Smith wrote:

...
Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

When you see yourself writing a function like this, you could write it like this instead: removeMaybeHash (Just ref) = ref removeMaybeHash Nothing = HashTable.new (==) (\key -> key)

Hopefully you agree this 2 line version is more clear. You could go further of course and use the function 'maybe' from the prelude, and pass the function 'id' instead of \key -> key, but I don't want to overwhelm you.

Good luck, Jason

Jason Dagit

1:22 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

On Mon, Apr 13, 2009 at 9:59 AM, John Smith wrote:

...

Yes, agreed. Got any clue on the original problem (except to use Data.Map)?

Nope. Sorry but your question is not something I have experience with. I don't know why, but I rarely use hashtables (in any language). Jason

Lennart Augustsson

1:45 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

res <- HashTable.lookup h 3 >>= maybe (return Nothing) (flip HashTable.lookup 1000) On Mon, Apr 13, 2009 at 6:59 PM, John Smith wrote:

...

Yes, agreed. Got any clue on the original problem (except to use Data.Map)?

On Mon, Apr 13, 2009 at 6:55 PM, Jason Dagit wrote:

...
Others have provided help to answer your question but I'd like to provide a little bit different feedback.

On Mon, Apr 13, 2009 at 8:42 AM, John Smith wrote:

...
Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

When you see yourself writing a function like this, you could write it like this instead: removeMaybeHash (Just ref) = ref removeMaybeHash Nothing = HashTable.new (==) (\key -> key)

Hopefully you agree this 2 line version is more clear. You could go further of course and use the function 'maybe' from the prelude, and pass the function 'id' instead of \key -> key, but I don't want to overwhelm you.

Good luck, Jason

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

John Smith

14 Apr 14 Apr

6:56 a.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Thanks, I was close, but the I was trying to use (something like) this statement without the return: maybe (return Nothing) (flip HashTable.lookup 1000) More or less like this: maybe (Nothing) (flip HashTable.lookup 1000) Which did't work... Guess the return is needed because we use a new monad (Maybe) inside another monad (IO). Petter On Mon, Apr 13, 2009 at 7:45 PM, Lennart Augustsson wrote:

...

res <- HashTable.lookup h 3 >>= maybe (return Nothing) (flip HashTable.lookup 1000)

On Mon, Apr 13, 2009 at 6:59 PM, John Smith wrote:

...
Yes, agreed. Got any clue on the original problem (except to use Data.Map)?

On Mon, Apr 13, 2009 at 6:55 PM, Jason Dagit wrote:

...
Others have provided help to answer your question but I'd like to provide a little bit different feedback.

On Mon, Apr 13, 2009 at 8:42 AM, John Smith wrote:

...
Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

When you see yourself writing a function like this, you could write it like this instead: removeMaybeHash (Just ref) = ref removeMaybeHash Nothing = HashTable.new (==) (\key -> key)

Hopefully you agree this 2 line version is more clear. You could go further of course and use the function 'maybe' from the prelude, and pass the function 'id' instead of \key -> key, but I don't want to overwhelm you.

Good luck, Jason

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Martijn van Steenbergen

13 Apr 13 Apr

2:26 p.m.

New subject: Types and hashes of hashes, trouble for a Java-programmer...

Jason Dagit wrote:

...

...
removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

When you see yourself writing a function like this, you could write it like this instead: removeMaybeHash (Just ref) = ref removeMaybeHash Nothing = HashTable.new (==) (\key -> key)

Hopefully you agree this 2 line version is more clear.

Actually, I prefer the other one... (though not necessarily spread out over 4 lines) I think this is more a matter of taste rather than clarity. Martijn.

Dan Doel

1:44 p.m.

On Monday 13 April 2009 11:42:33 am John Smith wrote:

...

Hi, a java-programmer running into trouble while trying to learn Haskell.

I try to make a hash containing hashes but can not getting a value out of the innermost hash - I keep running into type-trouble where IO and Maybe monad is getting mixed?

I don't know the type of all these things, but here's a try.

...

My attempt:

removeMaybeHash x = case x of Just ref -> ref Nothing -> HashTable.new (==) (\key -> key)

'HashTable.new ...' has type IO (HashTable k v). This means that the type of removeMaybeHash must be: Maybe (IO (HashTable k v)) -> IO (HashTable k v) because in the Just case, you're just using 'ref' as the result of the function. This is probably not what you want, so you should use 'return ref'. This will make it have type: Maybe (HashTable k v) -> IO (HashTable k v)

...

test = do h <- HashTable.new (==) (\key -> key) h1 <- HashTable.new (==) (\key -> key) HashTable.insert h 3 h1 HashTable.insert h1 1 1000 maybeOuterHash <- HashTable.lookup h 3 res <- removeMaybe (removeMaybeHash maybeOuterHash) 1000

I don't know what the type of removeMaybe is supposed to be, but as used in this expression, with the above note about the type of removeMaybeHash, it must have type: IO (HashTable k v) -> Int -> IO (something) which is an odd type for a function with name "removeMaybe".

...

return res

Any clues?

Hopefully those help. As an additional clue, I'd recommend you write some type signatures at the top level for what you expect the types of your functions to be. That might help point out more specifically where things aren't going as you expect. -- Dan

5882

Age (days ago)

5883

Last active (days ago)

List overview

Download

17 comments

8 participants

participants (8)

Achim Schneider
Dan Doel
Jason Dagit
John A. De Goes
John Smith
John Van Enk
Lennart Augustsson
Martijn van Steenbergen