Re: Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

On Mon, Jul 07, 2003 at 04:37:46PM +0100, Sarah Thompson wrote:

> I'd considered something like embedding the type in the IO monad, with 
> links between components implemented as IORefs, but I'd really prefer 
> something cleaner (pure functional). If the code ends up horribly 
> complicated in order to get decent performance, I might as well fold and 
> use C++ instead.

At the risk of stating the obvious, IORefs _are_ pure functional. :-)

> I'm currently wondering about going for an adjacency list approach (as
> used by most graph libraries), with the tuples in the adjacency list
> extended to include input/output labels, resulting in a 4-ary tuple
> rather than the usual 2-ary. But, I don't want to be stuck with
> representing this as a list -- I really need log N lookups or
> performance will stink horribly as circuits get big. Maybe a pair of
> finite maps, allowing the edges to be traversed in either direction?

You could do that.  Or you could use just one FiniteMap and reverse
the iterator before you use it.  (Remember that reverse is an amortised
O(1) operation, assuming you need to traverse the whole list.)

Or you could take a copy of the FiniteMap source code and add your own
reverse iterator to complement the forward iterator which is already 
there.  You could even submit a patch. :-)

Or you could use a different data structure, say, one with O(n)
iteration from either end, O(log n) search and O(1) insertion onto
either end.  There are several of these floating around.  This one
is quite good:

http://citeseer.nj.nec.com/25942.html

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

On Mon, Jul 07, 2003 at 04:04:17PM +0100, Sarah Thompson wrote:

> > I would also need to implement efficient indexes into the data structure 
> > -- flat searching will be too slow for non-trivial amounts of data. In 
> > C++, I'd implement one or more external (probably STL-based) indexes 
> > that point into the main data structure.

I replied:

> The direct Haskell equivalent is to use Refs; either IORefs or
> STRefs.  (I'd personally use IORefs, but that's because I like
> having IO around.)  Dereferencing an IORef is a constant-time
> operation, just like chasing a pointer in C.

I forgot to give an example. :-)

Suppose you want some kind of electronic circuit, as you suggested.
Abstractly, you want something like this:

data Node
  = Node NodeState [Component]

data Component
  = Resistor ResistorCharacteristics Node Node
  | Transistor TransistorCharacteristics Node Node Node
  | {- etc -}

You can make this indirect in introducing refs:

type NodeRef = IORef Node
type ComponentRef = IORef Component

data Node
  = Node NodeState [ComponentRef]

data Component
  = Resistor ResistorCharacteristics NodeRef NodeRef
  | Transistor TransistorCharacteristics NodeRef NodeRef NodeRef

The data structures are mutable:

getNodeState :: NodeRef -> IO NodeState
getNodeState node
  = do  Node state _ <- readIORef node
return state

setNodeState :: NodeRef -> NodeState -> IO ()
setNodeState node state
  = do  modifyIORef (\Node _ cs -> Node state cs) node

and it's straightforward to construct an index into the middle
somewhere:

type NamedNodeIndex = FiniteMap String NodeRef

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Andrew J Bromage]

G'day all.

As you note, some kind of indirection is what you want here.

On Mon, Jul 07, 2003 at 04:04:17PM +0100, Sarah Thompson wrote:

> I would also need to implement efficient indexes into the data structure 
> -- flat searching will be too slow for non-trivial amounts of data. In 
> C++, I'd implement one or more external (probably STL-based) indexes 
> that point into the main data structure.

The direct Haskell equivalent is to use Refs; either IORefs or
STRefs.  (I'd personally use IORefs, but that's because I like
having IO around.)  Dereferencing an IORef is a constant-time
operation, just like chasing a pointer in C.

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Andrew J Bromage]

G'day all.

On Mon, Jul 07, 2003 at 12:01:09PM +0200, Jerzy Karczmarczuk wrote:

> I don't understand the remark that the internal arithmetic is
> binary. Sure, it is, so what?

The reason is that you can get the Rational representation even
faster than using continued fractions. :-)

toFrac :: (RealFloat a) => a -> Rational
toFrac x
| m == 0= 0
| otherwise = fromInteger m * 2^^(toInteger n)
where (m,n) = decodeFloat x

Prelude> toFrac 0.1
13421773 % 134217728

Cheers,
Andrew Bromage
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Christopher Milton]

--- Sarah Thompson <[EMAIL PROTECTED]> wrote:
> What is the best way to represent cyclic data structures in Haskell?

You _might_ find some useful ideas in

Franklyn Turbak and J. B. Wells.  Cycle Therapy: A Prescription for Fold and
Unfold on Regular Trees.  Third International Conference on Principles and
Practice of Declarative Programming. ACM, 2001.
http://cs.wellesley.edu/~fturbak/pubs/ppdp01.html
http://cs.wellesley.edu/~fturbak/pubs/index.html

Stefan Kahrs. Unlimp: Uniqueness as a leitmotiv for implementation. In M.
Bruynooghe and M. Wirsing, editors, Proc. Programming Language Implementation
and Logic Programming, Lecture Notes in Computer Science 631, 115--129, 1992.
http://citeseer.nj.nec.com/kahrs92unlimp.html

Chris Milton
(busy processing MILSTRIPs in Perl)


=
Christopher Milton
[EMAIL PROTECTED]
¸ÅÃӤ䤫¤ï¤ºÈô¤Ó¹þ¤à¿å¤Î²»
--Matsuo Bashou
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Graham Klyne]

Lazy evaluation means that you can embed nodes directly in a cyclic 
structure, even though that would appear to create an indefinite 
regression.  In order to detect cycles, one might add a node 
identifier.  Here's a simple example:

[[
-- spike-cyclicstructure.hs
data Node = Node { nodeid :: String, adjacent :: [Node] }

instance Eq Node where n1 == n2 = nodeid n1 == nodeid n2

instance Show Node where show = nodeid

findPaths :: Node -> Node -> [[Node]]
findPaths fromNode toNode = map reverse $ findPaths1 [] fromNode toNode
findPaths1 :: [Node] -> Node -> Node -> [[Node]]
findPaths1 beenThere fromNode toNode
| fromNode == toNode = [fromNode:beenThere]
| otherwise = concat [ findPaths1 (fromNode:beenThere) nextNode toNode
 | nextNode <- adjacent fromNode
 , not ( nextNode `elem` beenThere ) ]
n1 = Node "n1" [n2,n3,n4]
n2 = Node "n2" [n1,n3,n4]
n3 = Node "n3" [n1,n2]
n4 = Node "n4" [n1,n2]
test1 = findPaths n1 n2 -- [[n1,n2],[n1,n3,n2],[n1,n4,n2]]
test2 = findPaths n1 n3 -- [[n1,n2,n3],[n1,n3],[n1,n4,n2,n3]]
]]
One (crude) way to think about this is that a mention of a value in haskell 
behaves in some ways like a pointer to that value in (say) C.

If you don't want to assign unique identifiers by hand, you could use a 
state transformer monad to generate them for you.

#g
--
At 16:37 07/07/03 +0100, Sarah Thompson wrote:

From reading your message, it seems you want a graph library of sorts.
The important bit is 'of sorts', unfortunately! Most graph libraries I've 
seen to date (although I must admit that they have been written in C and 
C++, including one I perpetrated personally) don't really work that well 
for circuits because, for anything other than trivially simple components, 
the connections between nodes need to be labelled.

A component representing something simple like (say) an 'and' gate would 
be easy enough to represent as a node of an ordinary directed graph. In 
such a case, an incoming arrow would always be an input of the gate, and 
an outgoing arrow would always be the output. I need to be able to 
represent more complex components, up to and including the complexity of 
things like CPUs, where you might have lots and lots of inputs and outputs 
with substantially different meanings. In the case of a CPU, it would 
never be acceptable to (for example) swap a chip select output for an 
address or data line.

This makes me think that an off-the-shelf graph library won't quite be 
what I'm after, so I will almost certainly need to write the code. What 
I'm more interested in at the moment is a view on the best kinds of 
approach that might be appropriate.

I'd considered something like embedding the type in the IO monad, with 
links between components implemented as IORefs, but I'd really prefer 
something cleaner (pure functional). If the code ends up horribly 
complicated in order to get decent performance, I might as well fold and 
use C++ instead.

I'm currently wondering about going for an adjacency list approach (as 
used by most graph libraries), with the tuples in the adjacency list 
extended to include input/output labels, resulting in a 4-ary tuple rather 
than the usual 2-ary. But, I don't want to be stuck with representing this 
as a list -- I really need log N lookups or performance will stink 
horribly as circuits get big. Maybe a pair of finite maps, allowing the 
edges to be traversed in either direction?


If FGL seems like overkill to you, I have my own little mini graph
library which basically looks like:
 - An ADT, Node:  newtype Node = Node Int deriving ...
 - The 'Graph n e' data structure, containing:
 - a FiniteMap from n -> Node
 - an (growable?) array of type IOArray (Node,Node) e
the array represents the edges in the top half (i do some index fiddling
to get this efficient) and the finitemap represents the node labellings.
It's a pretty stupid interface and works a lot better when the graphs
are fixed size (that way you don't need to grow the array).  But it
works.
The finite map from n to Node seems like a good idea. Does representing 
the adjacency list as a flat array cause any problems?

Sarah

--
--
   / __+ / Sarah Thompson   /
  / (_  _  _ _ |_   /* /
 /  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
/ +   / http://findatlantis.com/ /
--


--
 --
/ __+ / Sarah Thompson   /
   / (_  _  _ _ |_   /* /
  /  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
 / +   / http://findatlantis.com/ /
--
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
---
Graham Klyne
<[EMAIL PROTECTED]>
PGP: 0FAA 69FF C08

Re: Hugs Humor

[Jon Fairbairn]

On 2003-07-07 at 13:40+0200 Jerzy Karczmarczuk wrote:
> [...] I believe (still naïvely??) that those socio-psycho-pragmatisms
> which played some role in the definition of the language should
> be better tuned. If I were to write
> 
> pi = 3.1415926536 :: Rational
> 
> I suppose that I would like to see rather 355/113 or something close,
> than 3926990817/125000 or similar.

If it's a _Rational_, surely you want it to be exactly the
same as you get for 31415926536%100?

> GHCI doesn't make me happier than Hugs:
> 221069929751607/70368744177664.

That doesn't happen for me:

   Prelude> :m Ratio   
   Prelude Ratio> 31415926536%100
   3926990817 % 125000
   Prelude Ratio> 3.1415926536::Rational  
   3926990817 % 125000
   Prelude Ratio> 

What did you do to get it?
  
>  Thus, perhaps one day we might think about parametrizing
> the 'conversion' of *explicit* decimal numbers, and -- as
> some other language permit -- make it possible and
> practical to use any other base different from 10. What do
> you think?

There might be a use for that, but one can already write

   0x55%2^32

so I'm not sure that there would be much call for it, given
what I say below

> Such parametrization (perhaps with some global default)
> would also help the user who permits himself to write x =
> 1.875987 :: Rational to assess the error introduced by the
> representation conversion.

I think that  :: Rational ought not to
introduce any error at all!

As to exact v inexact numbers, in a sense we already have
that distinction. Integer and Rational are (in correct
implementations!) exact, Int, Float and Double are
inexact. One could express my objection to the design as:
relegate all inexactitudes to libraries.

Cheers,

  Jón

-- 
Jón Fairbairn [EMAIL PROTECTED]


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Sarah Thompson]

From reading your message, it seems you want a graph library of sorts.

The important bit is 'of sorts', unfortunately! Most graph libraries 
I've seen to date (although I must admit that they have been written in 
C and C++, including one I perpetrated personally) don't really work 
that well for circuits because, for anything other than trivially simple 
components, the connections between nodes need to be labelled.

A component representing something simple like (say) an 'and' gate would 
be easy enough to represent as a node of an ordinary directed graph. In 
such a case, an incoming arrow would always be an input of the gate, and 
an outgoing arrow would always be the output. I need to be able to 
represent more complex components, up to and including the complexity of 
things like CPUs, where you might have lots and lots of inputs and 
outputs with substantially different meanings. In the case of a CPU, it 
would never be acceptable to (for example) swap a chip select output for 
an address or data line.

This makes me think that an off-the-shelf graph library won't quite be 
what I'm after, so I will almost certainly need to write the code. What 
I'm more interested in at the moment is a view on the best kinds of 
approach that might be appropriate.

I'd considered something like embedding the type in the IO monad, with 
links between components implemented as IORefs, but I'd really prefer 
something cleaner (pure functional). If the code ends up horribly 
complicated in order to get decent performance, I might as well fold and 
use C++ instead.

I'm currently wondering about going for an adjacency list approach (as 
used by most graph libraries), with the tuples in the adjacency list 
extended to include input/output labels, resulting in a 4-ary tuple 
rather than the usual 2-ary. But, I don't want to be stuck with 
representing this as a list -- I really need log N lookups or 
performance will stink horribly as circuits get big. Maybe a pair of 
finite maps, allowing the edges to be traversed in either direction?


If FGL seems like overkill to you, I have my own little mini graph
library which basically looks like:
 - An ADT, Node:  newtype Node = Node Int deriving ...
 - The 'Graph n e' data structure, containing:
 - a FiniteMap from n -> Node
 - an (growable?) array of type IOArray (Node,Node) e
the array represents the edges in the top half (i do some index fiddling
to get this efficient) and the finitemap represents the node labellings.
It's a pretty stupid interface and works a lot better when the graphs
are fixed size (that way you don't need to grow the array).  But it
works.
 

The finite map from n to Node seems like a good idea. Does representing the adjacency list as a flat array cause any problems?

Sarah

--
--
   / __+ / Sarah Thompson   /
  / (_  _  _ _ |_   /* /
 /  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
/ +   / http://findatlantis.com/ /
--


--
 --
/ __+ / Sarah Thompson   /
   / (_  _  _ _ |_   /* /
  /  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
 / +   / http://findatlantis.com/ /
--
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Lex Stein]

Why not just use a GUID to represent each node. Then a C pointer just
becomes a GUID in a tuple alongside the node. The C pointer approach is
just a method to have the memory system dole out GUIDs. And it can be
generalised. Then all the tuples could be inserted in a hash table on the
GUID component. Edges are then tuples of two GUIDs.  These could be stored
in some other data structure.

Another approach would be to have a type (node * (guid list))  (excuse the
Ocaml syntax). Put elements of this type in a big array. The GUID of a
node (guid) is its array index. Each node is accompanied in the tuple by a
list of nodes that it points to.

You know your workload and whether you have advance knowledge of the
number of nodes, so you are in the position to compare the efficiency of
these 2 approaches.

Good luck
Lex

--
Lex Stein http://www.eecs.harvard.edu/~stein/
[EMAIL PROTECTED]TEL: 617-233-0246

On Mon, 7 Jul 2003, Sarah Thompson wrote:

> What is the best way to represent cyclic data structures in Haskell?
>
> Lists are trivial. Trees are trivial. But what if the thing you're
> trying to represent is shaped like an electronic circuit, with a
> (possibly large) number of nodes connected by multiple arrows to other
> nodes? In an imperative language like C++, I'd probably just model the
> circuit directly, with objects representing nodes and pointers
> representing links between nodes. A good way to model this in Haskell is
> less obvious, however.
>
> A simplistic approach would be to represent such a structure as a list
> of nodes, where each node contained a list of other connected nodes.
> Containing the actual nodes within the sub-lists probably isn't feasible
> -- some kind of reference would be necessary in order to get around
> chicken-and-egg problems with instantiating the data structure. But, in
> this case, it's not so easy to see how one could 'walk' the structure
> efficiently, because moving from node to node would involve quite
> horrible (possibly slow) lookups. In C++, I'd simply follow a pointer,
> which would be an extremely fast operation.
>
> I would also need to implement efficient indexes into the data structure
> -- flat searching will be too slow for non-trivial amounts of data. In
> C++, I'd implement one or more external (probably STL-based) indexes
> that point into the main data structure.
>
> How do people typically solve this problem at the moment? I know a few
> people out there have written hardware compilers in Haskell and similar
> languages, so there should be some experience of this in the community.
> I can probably work something out soon enough, but reinventing the wheel
> is never a great idea.
>
> Thank you in advance,
>
> --
>   --
>  / __+ / Sarah Thompson   /
> / (_  _  _ _ |_   /* /
>/  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
>   / +   / http://findatlantis.com/ /
>  --
>
>
> ___
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Representing cyclic data structures efficiently in Haskell

[Antony Courtney]

Hi Sarah,

Representing cyclic structures is indeed somewhat tricky in a pure 
functional language.  The obvious representation (representing the link 
structure implicitly in an algebraic data type) doesn't work, because 
you can't obvserve cycles.

I recommend checking out two pieces of work in this area:

1.  Martin Erwig's work on inductive representations of graphs:

  Inductive Graphs and Functional Graph Algorithms, Martin Erwig
  Journal of Functional Programming Vol. 11, No. 5, 467-492, 2001
available from:

  http://cs.oregonstate.edu/~erwig/papers/abstracts.html#JFP01

2.  Koen Claessen and David Sands' work on observable sharing:

  Observable Sharing for Functional Circuit Description,
Koen Claessen, David Sands, published at ASIAN '99, in Phuket, Thailand
available from:

  http://www.math.chalmers.se/~koen/Papers/obs-shar.ps

Hope that helps,

	-Antony

--
Antony Courtney
Grad. Student, Dept. of Computer Science, Yale University
[EMAIL PROTECTED]  http://www.apocalypse.org/pub/u/antony
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

RE: Representing cyclic data structures efficiently in Haskell

[Hal Daume]

>From reading your message, it seems you want a graph library of sorts.
I've used FGL extensively and found it to be very nice.  It even
provides both a purely functional interface as well as an
imperative-esque interface.  It also comes with a bunch of standard
algorithms built in, though I don't know enough about circuitry stuff to
know whether those would be useful or not.

If FGL seems like overkill to you, I have my own little mini graph
library which basically looks like:

  - An ADT, Node:  newtype Node = Node Int deriving ...
  - The 'Graph n e' data structure, containing:
  - a FiniteMap from n -> Node
  - an (growable?) array of type IOArray (Node,Node) e

the array represents the edges in the top half (i do some index fiddling
to get this efficient) and the finitemap represents the node labellings.
It's a pretty stupid interface and works a lot better when the graphs
are fixed size (that way you don't need to grow the array).  But it
works.

--
 Hal Daume III   | [EMAIL PROTECTED]
 "Arrest this man, he talks in maths."   | www.isi.edu/~hdaume


> -Original Message-
> From: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] On Behalf Of Sarah Thompson
> Sent: Monday, July 07, 2003 8:04 AM
> To: [EMAIL PROTECTED]
> Subject: Representing cyclic data structures efficiently in Haskell
> 
> 
> What is the best way to represent cyclic data structures in Haskell?
> 
> Lists are trivial. Trees are trivial. But what if the thing you're 
> trying to represent is shaped like an electronic circuit, with a 
> (possibly large) number of nodes connected by multiple arrows 
> to other 
> nodes? In an imperative language like C++, I'd probably just 
> model the 
> circuit directly, with objects representing nodes and pointers 
> representing links between nodes. A good way to model this in 
> Haskell is 
> less obvious, however.
> 
> A simplistic approach would be to represent such a structure 
> as a list 
> of nodes, where each node contained a list of other connected nodes. 
> Containing the actual nodes within the sub-lists probably 
> isn't feasible 
> -- some kind of reference would be necessary in order to get around 
> chicken-and-egg problems with instantiating the data 
> structure. But, in 
> this case, it's not so easy to see how one could 'walk' the structure 
> efficiently, because moving from node to node would involve quite 
> horrible (possibly slow) lookups. In C++, I'd simply follow a 
> pointer, 
> which would be an extremely fast operation.
> 
> I would also need to implement efficient indexes into the 
> data structure 
> -- flat searching will be too slow for non-trivial amounts of 
> data. In 
> C++, I'd implement one or more external (probably STL-based) indexes 
> that point into the main data structure.
> 
> How do people typically solve this problem at the moment? I 
> know a few 
> people out there have written hardware compilers in Haskell 
> and similar 
> languages, so there should be some experience of this in the 
> community. 
> I can probably work something out soon enough, but 
> reinventing the wheel 
> is never a great idea.
> 
> Thank you in advance,
> 
> -- 
>   --
>  / __+ / Sarah Thompson   /
> / (_  _  _ _ |_   /* /
>/  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
>   / +   / http://findatlantis.com/ /
>  --
> 
> 
> ___
> Haskell-Cafe mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Representing cyclic data structures efficiently in Haskell

[Sarah Thompson]

What is the best way to represent cyclic data structures in Haskell?

Lists are trivial. Trees are trivial. But what if the thing you're 
trying to represent is shaped like an electronic circuit, with a 
(possibly large) number of nodes connected by multiple arrows to other 
nodes? In an imperative language like C++, I'd probably just model the 
circuit directly, with objects representing nodes and pointers 
representing links between nodes. A good way to model this in Haskell is 
less obvious, however.

A simplistic approach would be to represent such a structure as a list 
of nodes, where each node contained a list of other connected nodes. 
Containing the actual nodes within the sub-lists probably isn't feasible 
-- some kind of reference would be necessary in order to get around 
chicken-and-egg problems with instantiating the data structure. But, in 
this case, it's not so easy to see how one could 'walk' the structure 
efficiently, because moving from node to node would involve quite 
horrible (possibly slow) lookups. In C++, I'd simply follow a pointer, 
which would be an extremely fast operation.

I would also need to implement efficient indexes into the data structure 
-- flat searching will be too slow for non-trivial amounts of data. In 
C++, I'd implement one or more external (probably STL-based) indexes 
that point into the main data structure.

How do people typically solve this problem at the moment? I know a few 
people out there have written hardware compilers in Haskell and similar 
languages, so there should be some experience of this in the community. 
I can probably work something out soon enough, but reinventing the wheel 
is never a great idea.

Thank you in advance,

--
 --
/ __+ / Sarah Thompson   /
   / (_  _  _ _ |_   /* /
  /  __)(_|| (_|| ) / [EMAIL PROTECTED]  * /
 / +   / http://findatlantis.com/ /
--
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: accessing Haskell-Cafe from oe

[Peter Simons]

Jeff Aimt writes:

 > [haskell-cafe via news server]

You can access the mailing list via NNTP under the name
gmane.comp.lang.haskell.cafe on news.gmane.org. See
 for further details.

Peter

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

accessing Haskell-Cafe from oe

[Jeff Aimt]

Hello,
 
I discovered recently (thanks google) that Haskell 
Cafe was also named "fa.haskell", but can't find a news server which would let 
me access it like any other newsgroup. If someone accesses haskell cafe using a 
free news server, could he say me which one ? 
 
Thanks by advance.

Re: Hugs Humor

[Jerzy Karczmarczuk]

Ross Paterson wrote:

In the case of 0.1::Rational, it shouldn't be using floating point.
The Report says this means fromRational (1%10), i.e. 1%10.


Aha. Now I have a little chance to die less naïve. All my conversion
proposals are simply out of place, since there should be nothing
to convert. And I understand the reluctance of Jón to accept the
numerical types as belonging to the language...
... and I begin once again to appreciate the Scheme idea of having
the distinction between exact and inexact numbers.
Of course, you are right reminding that when floats are engaged there
is fuzziness in the conversion:
> (e.g.: which approximant in the series should be chosen?)

but I believe (still naïvely??) that those socio-psycho-pragmatisms
which played some role in the definition of the language should
be better tuned. If I were to write
pi = 3.1415926536 :: Rational

I suppose that I would like to see rather 355/113 or something close,
than 3926990817/125000 or similar. GHCI doesn't make me happier than
Hugs: 221069929751607/70368744177664.  Thus, perhaps one day we might
think about parametrizing the 'conversion' of *explicit* decimal numbers,
and -- as some other language permit -- make it possible and practical
to use any other base different from 10. What do you think?
Such parametrization (perhaps with some global default) would also help
the user who permits himself to write x = 1.875987 :: Rational to
assess the error introduced by the representation conversion.
Jerzy Karczmarczuk



___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Ross Paterson]

On Mon, Jul 07, 2003 at 01:09:53PM +0200, Wolfgang Jeltsch wrote:
> On Monday, 2003-07-07, 13:05, CEST, Ross Paterson wrote:
> > In the case of 0.1::Rational, it shouldn't be using floating point. The
> > Report says this means fromRational (1%10), i.e. 1%10.
> 
> In which paragraph of the report is this specified?

I take that as the meaning of the part you're reading (6.4.1), though it
would be better if it said "the appropriate value" rather than "a value".
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Wolfgang Jeltsch]

On Monday, 2003-07-07, 13:05, CEST, Ross Paterson wrote:
> [...]

> In the case of 0.1::Rational, it shouldn't be using floating point. The
> Report says this means fromRational (1%10), i.e. 1%10.

In which paragraph of the report is this specified?

> [...]

Wolfgang

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Ross Paterson]

On Mon, Jul 07, 2003 at 12:01:09PM +0200, Jerzy Karczmarczuk wrote:
> This is less a bug than a Nessie monster which haunts Hugs
> some centuries already, and on Internet the issue has been
> discussed at least 4 times. The old, experimental Gofer
> Prelude numeric functions were sometimes abominable, since
> Mark Jones concentrated on other things, and nobody really
> complained, people were busy with other stuff as well.
> 
> But I can't understand why this continues until now. The
> obvious technique to convert floats to rationals is the
> continued fraction expansion which gives the simplified
> answer fast.

That would be because resources for Hugs maintenance are extremely
limited, and expertise in numerical methods even more lacking.
(e.g.: which approximant in the series should be chosen?)  I think
that if someone who knows about these things submitted a patch, and it
didn't increase the size of the Prelude (by much), it would be gratefully
accepted.  (That's probably true of all of Hugs.)

However, as far as I know, the outstanding numeric bugs in the Prelude are
- floating point literals of type Ratio t (mostly fixed in CVS), and
- the show instances for Float and Double (because the correct
  Numeric.showFloat would make the Prelude too large)

> I don't understand the remark that the internal arithmetic is
> binary. Sure, it is, so what?

In the case of 0.1::Rational, it shouldn't be using floating point.
The Report says this means fromRational (1%10), i.e. 1%10.
If Hugs implemented the Haskell definition directly, the question of
approximation wouldn't arise.  GHC does it that way, and usually removes
the fromRational at compile time, but Hugs isn't that clever.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Jon Fairbairn]

On 2003-07-07 at 12:01+0200 Jerzy Karczmarczuk wrote:
> Jon Fairbairn comments //Steffen Mazanek//:
> 
> >>Prelude> 0.1::Rational
> >>13421773 % 134217728
> >>Prelude> 13421773/134217728
> >>0.1
> >>
> >>I do not know how this fraction is calculated, but
> >>it does not fit my expectations :-)
> >  
> > Remember that internally arithmetic is binary, and that 0.1
> > can't be expressed exactly as a floating point number. I
> > think that's the explanation.
> 
> I don't understand the remark that the internal arithmetic is
> binary. Sure, it is, so what?

My comment was perhaps too brief. As far as I am concerned,
a constant with a decimal point in it should go like this:

C.DD...DD
  \__d__/ 

becomes fromRational (CDD...DD % 100...00)

and there's no problem in getting an accurate Rational (what
you say about conversions applies if the desired result is
some kind of float). However, if the conversion goes via
float, and I think doing that is a bug, the fact that 1/5
has an infinite expansion in binary explains the peculiar
numbers that Hugs produces in its Rational. It's an
explanation of what happens, not what should be!

During the revision of the report I said something to the
effect that Int, Float and Double do not belong in the
language proper. The suggestion was rejected for (I think)
sociological reasons, but I still stand by it. While they
should of course be provided in the standard libraries, they
only serve to confuse things as far as the language design
is concerned.

  Jón

-- 
Jón Fairbairn [EMAIL PROTECTED]
31 Chalmers Road [EMAIL PROTECTED]
Cambridge CB1 3SZ+44 1223 570179 (after 14:00 only, please!)


___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Wolfgang Jeltsch]

On Monday, 2003-07-07, 01:37, CEST, Andrew J Bromage wrote:
> [...]

> On Sat, Jul 05, 2003 at 07:43:18PM +0200, Steffen Mazanek wrote:
> > Prelude> 0.1::Rational
> > 13421773 % 134217728
>
> That's allowed.  The Rational only has to be correct to the limit of machine
> precision.  (Incidentally, if it's any help in working out how this Rational
> was computed, the denominator is 2^27.)

The Haskell 98 Report, § 6.4.1:
Similarly, a floating literal stands for an application of fromRational to
a value of type Rational (that is, Ratio Integer).
This only talks about "*a* value of type Rational", not about how this value 
is choosen for a given literal. But since it's a Rational, the most natural 
way seems to calculate an exact value. For a literal a1 ... an.b1 ... bm, the 
value could be a1 ... anb1 ... bm % (10 ^ m). Why isn't this forced by the 
standard?

> [...]

Wolfgang

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: Hugs Humor

[Jerzy Karczmarczuk]

Jon Fairbairn comments //Steffen Mazanek//:

Prelude> 0.1::Rational
13421773 % 134217728
Prelude> 13421773/134217728
0.1
I do not know how this fraction is calculated, but
it does not fit my expectations :-)
 
Remember that internally arithmetic is binary, and that 0.1
can't be expressed exactly as a floating point number. I
think that's the explanation.

Ok, ok, it is no bug...
No, I think it is a bug: 0.1 ought to be equivalent to
fromRational (1%10), but Hugs isn't intended for numerical
work. GHCi gets the right answer.


This is less a bug than a Nessie monster which haunts Hugs
some centuries already, and on Internet the issue has been
discussed at least 4 times. The old, experimental Gofer
Prelude numeric functions were sometimes abominable, since
Mark Jones concentrated on other things, and nobody really
complained, people were busy with other stuff as well.
But I can't understand why this continues until now. The
obvious technique to convert floats to rationals is the
continued fraction expansion which gives the simplified
answer fast.
I don't understand the remark that the internal arithmetic is
binary. Sure, it is, so what? Why Ross Paterson underlies
this as well? He concludes:
> The real fix would be to keep the literals as Rationals, but
> this would be too expensive in the Hugs setting.
Andrew Bromage says some words about errors and representation.
I think that the problem can (perhaps should) be dealt with at
a higher level. What's wrong with conversion functions like
those below. First, convert a float to a lazy list of coeffs.
of a regular continued fraction:
tocfrac x =
 let n = floor x
 y = x-fromInteger n
 in n : if y==0.0 then [] else tocfrac (recip y)
and then reconstruct using Euler sequences as described in
Knuth or perhaps an optimized method, the one I cite is not
very efficient. It gives a list of (N,D) -- *all* rational
approximants of the original float.
continuant l@(_:ql) = zip (tail (euseq l)) (euseq ql)
 where
   euseq [] = []
   euseq (x:q) = eus 1 x q
   eus p0 p1 (a:cq) = p0 : eus p1 (a*p1+p0) cq
   eus p0 p1 [] = [p0,p1]


Now, test it:

pp=3.141592653589793
r=take 10 (continuant (tocfrac pp))
You should get

[(3,1),(22,7),(333,106),(355,113),(103993,33102),(104348,33215), ...
etc;, anyway all that is already inexact...
For 0.1 one gets [(0,1),(1,10)]

Jerzy Karczmarczuk

___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe