- Haskell-Cafe - Haskell.org

Representing cyclic data structures efficiently in Haskell
by Sarah Thompson 08 Jul '03

08 Jul '03

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 **** / / (_ _ _ _ |_ / * / / __)(_|| (_|| ) / sarah(a)telergy.com * / / + / http://findatlantis.com/ / ----------------------------------------------

6 6

RE: Representing cyclic data structures efficiently in Haskell
by Hal Daume 07 Jul '03

07 Jul '03

>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 | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: haskell-cafe-admin(a)haskell.org > [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Sarah Thompson > Sent: Monday, July 07, 2003 8:04 AM > To: haskell-cafe(a)haskell.org > 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 **** / > / (_ _ _ _ |_ / * / > / __)(_|| (_|| ) / sarah(a)telergy.com * / > / + / http://findatlantis.com/ / > ---------------------------------------------- > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Mailing Lists - Fax Directory - Company Databases
by Peter Cororan 06 Jul '03

06 Jul '03

We can supply you with UK mailing lists, Fax Directories and Company Databases, in any format that you specify. If you would like FREE sample data, please go to our web site www.ukdata.ndirect.co.uk Thank you Peter Cororan cororan(a)ndirect.co.uk

1 0

ucuz arama
by NETTEALO 05 Jul '03

05 Jul '03

1 0

Worldwide Partners program
by The TechNews 05 Jul '03

05 Jul '03

The TechNews, July 2003 Production Mini-plants in mobile containers. Worldwide Partners program Science Network will supply to countries and developing regions the technology and necessary support for production in series of Mini-plants in mobile containers (40-foot). The Mini-plant system is designed in such a way that all the production machinery is fixed on the platform of the container, with all wiring, piping, and installation parts; that is, they are fully equipped... and the mini-plant is ready for production." More than 700 portable production systems: Bakeries, Water purification, Dehydrated food, Steel Nails, Fruit juice preparation, Tire Retreading, Reinforcement Bar Bending for Construction Framework, Sheeting for Roofing, Ceilings and Façades, Plated Drums, Aluminum Buckets, Injected Polypropylene Housewares, Pressed Melamine Items (Glasses, Cups, Plates, Mugs, etc.), Mufflers, Construction Electrically Welded Mesh, Plastic Bags and Packaging, Mobile units of medical assistance, Sanitary Material, Hypodermic Syringes, Hemostatic Clamps, etc. Science Network has started a Co-investment program for the installation of small Assembly plants to manufacture in series the Mini-plants of portable production on site, region or country where required. One of the most relevant features is the fact that these plants will be connected to the World Trade System (WTS) with access to more than 50 million raw materials, products and services and automatic transactions for world trade. Due to financial reasons, involving cost and social impact, the best solution is setting up assembly plants on the same countries and regions, using local resources (labor, some equipment, etc.) Science Network participates at 50% (fifty percent) for investment of each Assembly plant. If you are interested in being a Science Network partner in your country or region, you can send your CV to: Mini-plants <A HREF="mailto:letters@the-tech-news.com">Worldwide Partners program</A> By Robert B. Lethe, The TechNews, Editor ------------------------------------------------------------------------- If you received this in error or would like to be removed from our list, please return us indicating: remove or un-subscribe in subject field, Thanks. <A HREF="mailto:editor@the-tech-news.com"> Editor</A> © 2003 The TechNews. All rights reserved.

1 0

FFI Ptr question
by paul＠theV.net 03 Jul '03

03 Jul '03

If a C function returns a (void*), let's say: data MyObj = MyObj foreign import ccall "static myobj_ffi.h new_obj" newMyObject :: IO (Ptr MyObj) ptr <- newMyObject should I free the ptr afterwards or not? If I have another imported C function: foreign import ccall "static myobj_ffi.h print_obj" printMyObject :: Ptr MyObj -> IO () Can I safely assume the C function print_obj(void *) always get the same pointer even if I call (printMyObject ptr) multiple times? Any hints is greatly appreciated! Regards, .paul.

4 7

-------|�Ż��|------
by webmaster 03 Jul '03

03 Jul '03

�װ��ѣ� ��ã� ��б��Ƽ��޹�˾��ʺ��л��տ��ʼ��ϵ�ϣ�� ܳ�Ϊ��ڹ��Ҫ��顣��һ�Ҳ��¼��ᾧ��о��ƹ�ͷ�չ �¼��ڻ��Ϣ��ע��ĸ��¼��ҵ�� :http://www.host-china.com ��˾��2003��ȫ��ʻ��Ƴ��²�Ʒ��пռ䶼֧�� ݿ⣨linux+PHP+Mysql;NT+asp+acess��⽫��ֵ��ѡ�� 1.30M�ռ�+30M��ҵ�ʾ� + ��һ�� ȫ�棬��198Ԫ/�ꡣ ��2.120M�ռ䣫120M��ҵ��䣫1��ȫ�棬��336Ԫ/�ꡣ 3.200M�ռ䣫50M��ҵ��䣫1��ȫ�棬��450Ԫ/�ꡣ 4.300M�ռ䣫50M��ҵ��䣫1��ȫ�棬��580Ԫ/�ꡣ �� Ǿ��Ϊ��ṩ��õķ��񡣣��ų��ʧ��Ը�� ˿Ҳ��Ϊ��һ��Ĳ��ġ��ǳ�ŵ��ⰴʵ�� ˿�벻Ҫֱ�ӻظ�,�ظ��뷢:jinjin732@sohu.com ��ף��ģ�˳�� webmaster of http://www.host-china.com ��б��Ƽ��޹�˾ http://www.host-china.com �绰��0592-5915491��ߣ� 0592-5652685�� 棺0592-5652687�� ϵ�ˣ�� С�� --------------------------------------------------------------- �е�Ⱥ��ʼ�,��ר��(http://www.21cmm.com) ��CMM��У(http://www.21cmm.com)��Ŀ��ר��

1 0

RE: haskell array access
by Simon Peyton-Jones 01 Jul '03

01 Jul '03

| Are there any concoctions of flags/pragmas/techniques to coax GHC into | unrolling a function (or rather an IO computation in this case) a couple | of iterations. There was another (admittedly also noddy) program that I | could get to near gcc, but only by unrolling by hand (though Ian's TH | stuff likely could have done it). GHC generally doesn't unroll recursions. The inliner runs repeatedly, so it's hard for it to know how much it unrolled "last time". (There's a paper "Secrets of the GHC inliner" on my publications page.) Simon

1 0

UML diagrams of Haskell
by Bas van Dijk 30 Jun '03

30 Jun '03

Hi, It's maybe a weird question but do there exist UML diagrams of the Haskell language. They don't necessarily have to be UML diagrams, as long as they show the different concepts in the language (i.e.: functions, datatypes, patterns, etc.) and the relations between them(i.e.: a function consists of other functions, functions have a type). Bas.

2 1

RE: Arrow Classes
by Simon Peyton-Jones 30 Jun '03

30 Jun '03

It may interest you guys to know that Ross Paterson and I have just put syntactic support for arrows into GHC. It's only in the CVS version at the moment, and is not documented at all, but those things will come. The type error messages should, I hope, be a lot better than those one can get by type checking pre-processed code. Simon | -----Original Message----- | From: haskell-cafe-admin(a)haskell.org [mailto:haskell-cafe-admin@haskell.org] On Behalf Of Joe | English | Sent: 28 June 2003 17:01 | To: haskell-cafe(a)haskell.org | Subject: Re: Arrow Classes | | | Ashley Yakeley wrote: | > Wolfgang Jeltsch wrote: | > | > > This brings me to another point. One year ago we had a discussion on The | > > Haskell Mailing List concerning arrows. (The subject of the mails was just | > > "arrows".) The point was that it seemed strange to me that first and second | > > are included in the basic arrow class Arrow while left and right have their | > > extra class ArrowChoice. Not only that it seemed strange to me but it made | > > impossible to make Parser baseMonad an instance of Arrow. Parser baseMonad | > > has nice implementations of pure and (>>>) but none of first or second. | > | > I agree. My own Arrow module hierarchy looks more or less like this: | > | > class Compositor comp where [...] | > class (Compositor arrow) => Arrow arrow where [...] | > class (Arrow arrow) => ProductArrow arrow where [...] | > class (Arrow arrow) => CoproductArrow arrow where [...] | > class (ProductArrow arrow,CoproductArrow arrow) => FullArrow arrow | > instance (ProductArrow arrow,CoproductArrow arrow) => FullArrow arrow | > class (Arrow arrow) => ArrowFix arrow where [...] | > class (FullArrow arrow) => ApplyArrow arrow where [...] | | | On that topic, see below for what mine looks like | (from HXML, <URL: http://www.flightlab.com/~joe/hxml/ >). | | I started off with Hughes' conventions, but for some | reason could never remember the difference between &&& and ***, | or between ||| and +++. I found &&&, >&<, |||, >|< to have | better mnemonic value. This also frees up +++ for ArrowPlus, | which -- in HXML applications -- is frequently used and should | thus be easy to type. | | When using the ArrowChoice operators, I kept tripping over all | the 'Either' coproduct types, so added some syntactic sugar | (borrowed from HaXML): | | data Choice a = a :> a | class (Arrow a) => ArrowChoice a where | [ ... ] | ( ?>) :: (b -> Bool) -> Choice (a b c) -> a b c | (>?>) :: a b Bool -> Choice (a b c) -> a b c | | I found "p ?> f :> g" much more pleasant to use. | | (I also like the idea of splitting the product operators out of | the base Arrow class -- will consider doing that in my library). | | -- | | infixr 5 +++ | infixr 3 >&<, &&& | infixr 2 >|<, |||, ?>, >?>, :> | infixl 1 >>> | | class Arrow a where | arr :: (b -> c) -> a b c | (>>>) :: a b c -> a c d -> a b d | apfst :: a b c -> a (b,x) (c,x) | apsnd :: a b c -> a (x,b) (x,c) | (>&<) :: a b c -> a d e -> a (b,d) (c,e) | (&&&) :: a b c -> a b d -> a b (c,d) | liftA2 :: (b -> c -> d) -> a e b -> a e c -> a e d | aConst :: c -> a b c | idArrow :: a b b | -- Minimal implementation: arr, >>>, apfst or >&< | | data Choice a = a :> a | class (Arrow a) => ArrowChoice a where | apl :: a b c -> a (Either b d) (Either c d) | apr :: a b c -> a (Either d b) (Either d c) | (>|<) :: a b c -> a d e -> a (Either b d) (Either c e) | (|||) :: a b c -> a d c -> a (Either b d) c | ( ?>) :: (b -> Bool) -> Choice (a b c) -> a b c | (>?>) :: a b Bool -> Choice (a b c) -> a b c | -- Minimal implementation: >|< or apl | | class (Arrow a) => ArrowApply a where | app :: a (a b c,b) c | | class (Arrow a) => ArrowZero a where | aZero :: a b c | aMaybe :: a (Maybe c) c | aGuard :: (b -> Bool) -> a b b | | class (Arrow a) => ArrowPlus a where | (+++) :: a b c -> a b c -> a b c | | | | --Joe English | | jenglish(a)flightlab.com | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0