- Haskell - Haskell.org

quantum search algorithm
by Jan Skibinski 13 Mar '01

13 Mar '01

Directly from the oven :-): http://www.numeric-quest.com/haskell/QuantumSearch.hs Excerpt from a short module description is given below. Jan Grover's algorithm assumes that one is given a quantum function, also called an oracle, that indicates, when confronted with any number between 0 and N-1, whether this number is or is not the special number being sought. The algorithm enables one to find a marked item in unstructured N-item database in a time that scales not as N, as a classical computer would require, but only as sqrt N. Putting it another way: the maximum number of calls to oracle is proportional to sqrt N. Think about a scenario when the oracle charges you per call, or when its computations are very lengthy. The answer is probabilistic, but given with very high degree of probability. In our implementation the 'search' function is able to find specifically marked number from the assemble of 8 numbers: 0..7 in just two calls to oracle, with very high degree of probability. The 'test' performs m such searches. Note that the final stage of the search is simulated as a quantum measurement performed on the state vector.

1 0

Laws for Monad and MonadPlus.
by Theodore Norvell 13 Mar '01

13 Mar '01

Hi all. I was revising a short article I've written about Monads in Haskell and started wondering about the identities associated with Monads. I think it is generally agreed (and in the report) that the following identities should be true of a Monad: Left identity: return a >>= k = k a Right identity: p >>= return = p Associativity: (p >>= j) >= k = p >>= (\x->(j x >>= k)) [provided x is not free in j or k] What about MonadPlus? By analogy with semirings, I came up with: Zero: mzero >>= k = mzero = p >>= (\x -> mzero) Identity: p `mplus` mzero = p = mzero `mplus` p Commutativity: p `mplus` q = q `mplus` p Right distributivity: (p `mplus` q) >>= k = (p >>= k) `mplus` (q >>= k) Left distributivity: p >>= (\x->j x `mplus` k x) = (p >>= j) `mplus` (p >== k) [provided x is not free in j or k] But commutativity does not hold for Maybe or [], left distributivity does not hold for Maybe and right distributivity does not hold for [], so these can't be right. Are the other identities I've listed ok? Are there other identities that I've missed? Cheers, Theodore Norvell ---------------------------- Dr. Theodore Norvell theo(a)engr.mun.ca Electrical and Computer Engineering http://www.engr.mun.ca/~theo Engineering and Applied Science Phone: (709) 737-8962 Memorial University of Newfoundland Fax: (709) 737-4042 St. John's, NF, Canada, A1B 3X5

2 2

Research Assistant/PhD Vacancy
by nipkow＠informatik.tu-muenchen.de 13 Mar '01

13 Mar '01

TOOL SUPPORT FOR LOGICAL CALCULI Research Assistant/PhD Vacancy Technical University Munich The theorem proving group (http://www4.in.tum.de/~kleing/group/group.html) at the Technical University Munich is looking for a research assistant to join a DFG-funded project focussing on the development and application of the theorem prover Isabelle (http://isabelle.in.tum.de) The position offers exciting opportunities for scientifically challenging research leading to a PhD. The appointment is initially for 2 years with an optional extension. We seek a candidate with a strong background in at least one of the following areas - theorem proving - logic - semantics of programming languages - functional/logic programming - specification languages who should like to work on the boundary between theory and practice. Depending on the candidates interests and abilities, the work can focus an either of the following areas: - logical calculi for the development of (object oriented) programs - structuring mechanisms for large theories - tool support for automated reasoning Informal inquiries and formal applications should be addressed to nipkow(a)in.tum.de (http://www.in.tum.de/~nipkow)

1 0

guiding strictness/lazyness through the program
by andreas.marth＠daimlerchrysler.com 13 Mar '01

13 Mar '01

Hallo! Does anybody know of a paper that describes ways how to force strict evaluation at some places and lazy evaluation at others? And I am also interested in a guideline when to use strict evaluation and when lazy. Any pointers appreciated! Thanks, Andreas

1 0

fold and unfold
by Graham Hutton 13 Mar '01

13 Mar '01

Dear all, The following new paper may be of interest to some readers of this group: When is a Function a Fold or an Unfold? Jeremy Gibbons, Graham Hutton, and Thorsten Altenkirch http://www.cs.nott.ac.uk/~gmh/when.pdf http://www.cs.nott.ac.uk/~gmh/when.ps We give a necessary and sufficient condition for when a set-theoretic function can be written using the recursion operator fold, and a dual condition for the recursion operator unfold. The conditions are simple, practically useful, and generic in the underlying datatype. (To appear in the Proceedings of the 4th International Workshop on Coalgebraic Methods in Computer Science, Genova, Italy, April 2001.) Best wishes, Graham +-----------------------------------------------------------------------------+ | Dr Graham Hutton Email : gmh(a)cs.nott.ac.uk | | Languages and Programming Group Web : http://www.cs.nott.ac.uk/~gmh/ | | School of Computer Science and IT | | The University of Nottingham | | Jubilee Campus, Wollaton Road | | Nottingham NG8 1BB | | United Kingdom | +-----------------------------------------------------------------------------+

1 0

Re: newbie
by edrx＠inx.com.br 13 Mar '01

13 Mar '01

Frank Atanassow wrote: > G Murali wrote (on 09-03-01 00:43 +0000): > > I'm new to this monads stuff.. can you tell me what it is simply ? > > an example would be highly appreciated.. i want it is very very > > simple terms please.. > > A monad on category C is a monoid in the category of endofunctors on C. > > Is that simple enough? ;) > > No? Then see "Using Monads" at http://haskell.org/bookshelf/ > > (Sorry, I just couldn't resist!) Uh-oh. I'm a junior categorist and toposopher and I confess that all my few attempts to understand what Haskell's monads have to do with the categorical notion of a monad have failed more or less miserably. Can someone point me to a relevant paper, or give a quick explanation? Thanks in advance, and sorry for the dumb question, Eduardo Ochs http://angg.twu.net/ edrx(a)inx.com.br

4 4

Any in Haskell Report
by Simon Peyton-Jones 12 Mar '01

12 Mar '01

Folks, In the Haskell Report, Feliks points out: | On pp. 5 and 120 the rule for "ANYseq" has a very strange | structure: why the | "{ANY}" at the beginning and end of the subtracted stuff? It | seems it could | be simplified, or at least explained. I have no idea why it can't be just ANYseq -> {ANY}_<opencomment | closecomment> Can anyone see why this simpler form would not work? I propose to adopt this simplification. Simon

2 1

Re: newbie
by Frank Atanassow 12 Mar '01

12 Mar '01

> On Fri, 9 Mar 2001, Frank Atanassow wrote: > > A monad on category C is a monoid in the category of endofunctors on C. Surprisingly, my facetious little remark about monads elicited the following response (whose author I will not disclose, as I haven't obtained permission yet): Somebody wrote (on 09-03-01 15:38 +0000): > Hi Frank --- Believe it or not your one-liner actually *is* helpful to me. > >From dim & distant algebra days I remember the definition of monoid (set, > binary operation, associative, left & right unit) but being a Physics > major/Maths minor, a long time ago, I was deprived of any introduction to > Category Theory. I've read some of the papers Haskell monads section & > also had a look at some category theory books --- but I can't remember > seeing your nice one-line definition --- do you have a reference to the > paper or book(s) that do it this way? I think the monoidal characterization is well known. I first saw it in Asperti & Longo [1] (p.75), but I'm sure it can be found in other texts. The connection with monoids is not very evident in Haskell, but is worth keeping in mind if you know a bit of category theory. BTW, part of the reason I'm posting this to the Haskell list is to plug a little project I have started on my home page. It's a small collection of useful reference texts which deal with programming languages and semantics, all of which have become available on the web. [1] is among these. <start violins for impassioned plea> I occasionally see posts on this list from people who are not researchers or educators (and consequently do not have ready access to such published material) expressing some interest in exploring PL theory and other, related formal topics further, if only the ``barrier-to-entry'' were not so high. Indeed, there is a wealth of technical articles which are available online, and could prove useful or at least interesting to many Haskell and ML programmers, but even the ones directed at a relatively wide audience of PL researchers can be hard to grasp for non-researchers. Personally, I think this is one reason that Haskell and ML are still fairly marginalized languages. My hope is that this list can grow into a useful resource for go-getters and self-starters from other fields and communities, as well as the average PL researcher. <end violins for impassioned plea> OK, I am only a stupid PhD student with no publications under my belt, but anyhow that is how I felt before I became a researcher. Over the space of a few years, while I was still hacking C++ in the dungeons of our vast corporate megacomplex, I laid out several hundred dollars of my own money to buy enough texts to jumpstart my own education, and what started with one book soon exploded into a mini-library of hardbacks and articles (because you know the dependencies in any non-trivial bibliography resemble a large bowl of sticky spaghetti), and I would have been deliriously happy to learn that, for example, Barendregt's encyclopaedic book on lambda-calculus was actually readable from the web. So here's to you, my comrades-in-arms. As it states on my page, if any of you know of any other relevant texts which might be added to the list, please contact me and I will augment the list forthwith. The list is available at: http://www.cs.uu.nl/people/franka/ and here is the reference I promised: [1] Andrea Asperti and Giussepe Longo. Categories, Types and Structures. An introduction to Category Theory for the working computer scientist. MIT Press, 1991. URL: http://www.dmi.ens.fr/users/longo/download.html Regards, -- Frank Atanassow, Information & Computing Sciences, Utrecht University Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands Tel +31 (030) 253-3261 Fax +31 (030) 251-379

1 1

list of results monad
by G Murali 12 Mar '01

12 Mar '01

hi, I'm trying to build a monad that will give a list of results. this is what i want to be able to do I have data M a = I [a] instance Monad M where return x = I [x] I (x:xs) >>= f = ?? The type of >>= is m a -> (a -> m b) -> m b but here the input is [a], now if I apply the input individually on f then i can get a [m b] and if i extract at each step then I can get [b] and then if i say return ([b]) i get m b.. right ?? Is this how I go about it .. if so can you give me a small code snippet of how to do that. Thanks, gmu _________________________________________________________________________ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.

3 2

RE: exception handling..
by Simon Peyton-Jones 12 Mar '01

12 Mar '01

http://research.microsoft.com/~simonpj/papers/marktoberdorf.ps.gz http://research.microsoft.com/~simonpj/Papers/except.ps.gz http://research.microsoft.com/~simonpj/papers/asynch-exns.ps.gz | -----Original Message----- | From: G Murali [mailto:gmu@hotmail.com] | Sent: 09 March 2001 23:15 | To: haskell(a)haskell.org | Subject: exception handling.. | | | Hi, | | Is it possible to do/mimic exception handling in Haskell | using monads.. if | so can you throw in some pointers on this please.. | | gmu | ______________________________________________________________ | ___________ | Get Your Private, Free E-mail from MSN Hotmail at | http://www.hotmail.com. | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell |

1 0