[Haskell-cafe] How to give unique name/id to nodes outside any monad ?

Luke Palmer lrpalmer at gmail.com
Thu Jan 8 04:04:36 EST 2009


On Thu, Jan 8, 2009 at 1:49 AM, minh thu <noteed at gmail.com> wrote:

> I'd like to simply write, like above,
>
> b = B a a where a = A [C]
>
> or, maybe,
>
> b = B label a a where a = A label [C]
>
> The question is : how can label be different each time ?


Haskell is pure, so I can answer this precisely:  obviously you cannot.
Sharing is *not* observable in Haskell, because it breaks referential
transparency, a very important property.

So what I meant by hashing was, eg.:

  newtype Hash = ...
  data Foo = Foo Hash Int [Foo]

  mkFoo :: Int -> [Foo] -> Foo
  mkFoo n xs = Foo (hash (show n ++ concatMap (\(Foo h _ _) -> show h))) n
xs

  hash :: String -> Hash
  hash = ... -- some cryptographic hash function

Probably going through Strings is not the smartest way, but you get the
idea?

Then when two Foos have the same hash, you have odds of 1/2^64 or whatever
that they are the same object.  You could also compare directly without
hashes, but that is slower for large data structures (more correct though --
hash comparisons always gave me the creeps).

I just saw your reply to the StableName suggestion.  I should warn you --
you should use this information only for optimization internal to your
program.  If you use it for observable effects, e.g. generating code or
writing to a file[1], you are writing *bad haskell*, and you will not only
lose the benefits of Haskell's purity, but you will be bitten by the
unpredictable zeal of the optimizer.

Luke

[1] Unless you read the file back into the data structure, where the sharing
is once again not observable.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090108/d8eb3bcb/attachment.htm


More information about the Haskell-Cafe mailing list