- Haskell - Haskell.org

modern arrays library
by Bulat Ziganshin 09 Jan '06

09 Jan '06

Hello i just published the following text at the http://haskell.org/haskellwiki/Arrays Haskell'98 supports just one array constructor type, namely Array (see http://haskell.org/onlinereport/array.html) It creates immutable boxed arrays. "Immutable" means that these arrays, like any other pure functional data structures, have contents fixed at construction time - you can't modify it, only query. There is a "modification" operations, but they just return new array and don't modify an original one. This makes possible using Arrays in pure functional code along with lists. "Boxed" means that array elements are just ordinary Haskell (lazy) values, which are evaluated on need, and even can contain bottom (undefined) value. You can learn how to use these arrays at http://haskell.org/tutorial/arrays.html and i recommend you to read this before proceeding to rest of this page Nowadays three Haskell compilers - GHC, Hugs and NHC - shipped with the same set of Hierarchical Libraries (http://www.haskell.org/ghc/docs/latest/html/libraries/index.html) and these libraries contains new implementation of arrays, which is backward compatible with the H98 one, but contains far more features. Suffice to say that these libraries supports 9 types of array constructors: Array, UArray, IOArray, IOUArray, STArray, STUArray, DiffArray, DiffUArray and StorableArray. It is no wonder that new arrays library make so much confusion for haskellers, although basically it is very simple - it provides only two interfaces, one of that you already know. Thus, the first interface, provided by the new arrays library, defined by type class IArray (which stands for "immutable array" and defined in module Data.Array.IArray - see http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-IArra…) and contains just the same operations that was defined for Array in H98. The only difference is that now it is a typeclass and there are 4 array type constructors, which implement this interface: Array, UArray, DiffArray, DiffUArray. We will describe later differences between them and cases when other types are preferred to use instead of good old Array. Also note that to use Array type constructor together with other new array types, you need to import Data.Array.IArray module instead of Data.Array > Mutable IO arrays (module Data.Array.IO) Second interface defined by the type class MArray (which stands for "mutable array" and defined in module Data.Array.MArray - see http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-MArra…) and contains operations to update array elements in-place. Mutable arrays are very like to IORefs, only containing multiple values. Type constructors for mutable arrays are IOArray and IOUArray and operations which create, update and query these arrays all belongs to IO monad: import Data.Array.IO main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int) readArray arr 1 >>= print writeArray arr 1 64 readArray arr 1 >>= print This program creates array of 10 elements with 37 as initial values. Then it reads and prints first element of array. After that program modifies first element of array and then reads and prints it again. Type definition in second line is necessary because our little program don't allow compiler to determine concrete type of `arr`. > Mutable arrays in ST monad (module Data.Array.ST) Just like IORef has more general cousine - STRef, IOArray has more general version - STArray (and IOUArray dubbed by STUArray). These array types allows to work with modifiable arrays in state monad: import Control.Monad.ST import Data.Array.ST main = print $ runST (do arr <- newArray (1,10) 127 :: ST s (STArray s Int Int) a <- readArray arr 1 writeArray arr 1 216 b <- readArray arr 1 return (a,b) ) Believe you or not, but now you know all that needed to _use_ any array type. Unless you are interested in speed issues, just use Array, IOArray and STArray where appropriate. The following topics are almost exclusively about selecting proper array type to make program run faster. > DiffArray (module Data.Array.Diff) As we already stated, update operation on immutable arrays (IArray) just creates new copy of array, what is very inefficient, but it is pure operation what can be used in pure functions. On the other hand, updates on mutable arrays (MArray) are efficient but can be done only in monadic code. DiffArray combines the best of both worlds - it supports interface of IArray and therefore can be used in pure functional way, but internally used an efficient updating of MArrays. How that trick works? DiffArray has pure external interface, but internally it represented as the reference to IOArray. When the '//' operator is applied to a diff array, its contents are physically updated in place. The old array silently changes its representation without changing the visible behavior: it stores a link to the new current array along with the difference to be applied to get the old contents. So if a diff array is used in a single-threaded style, i.e. after '//' application the old version is no longer used, @a'!'i@ takes O(1) time and @a '//' d@ takes O(@length d@). Accessing elements of older versions gradually becomes slower. Updating an array which is not current makes a physical copy. The resulting array is unlinked from the old family. So you can obtain a version which is guaranteed to be current and thus have fast element access by @a '//' []@. Library provides two "differential" array costructors - DiffArray, made internally from IOArray, and DiffUArray, based on IOUArray. But if you need, you can construct new "differential" array types from any 'MArray' types living in the 'IO' monad. See the module internals for further details > Unboxed arrays Unboxed arrays are like arrays in C - they contains just the plain values without extra level of indirection, so that, for example, array of 1024 values of type Int32 will use only 4 kb of memory. Moreover, indexing of such arrays works significantly faster. Of course, unboxed arrays have their own disadvantages. First, unboxed arays can be made only of plain values having fixed size - Int, Word, Char, Bool, Ptr, Double (see full list on http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-Unbox…) You can even implement yourself unboxed arrays interface for other simple types, including enumerations. But Integer, String and any other types defined with variants cannot form the unboxed arrays. Second, all elements in unboxed array are evaluated when array is created, so you can't use benefits of lazy evaluation for elements of such array. Nevertheless, unboxed arrays are very useful optimization instrument, so i recommend to use them as much as possible. All main array types in this library has their unboxed counterparts: Array - UArray (module Data.Array.Unboxed) IOArray - IOUArray (module Data.Array.IO) STArray - STUArray (module Data.Array.ST) DiffArray - DiffUArray (module Data.Array.Diff) So, basically replacing boxed arrays in your program with unboxed ones is very simple - just add 'U' to type signatures and you are done! If you changed Array to UArray, you also need to add "Data.Array.Unboxed" to your imports list > StorableArray (module Data.Array.Storable) A storable array is an IO-mutable array which stores its contents in a contiguous memory block living in the C heap. Elements are stored according to the class 'Storable'. You can obtain the pointer to the array contents to manipulate elements from languages like C. It is similar to 'IOUArray' (in particular, it implements the same MArray interface) but slower. Its advantage is that it's compatible with C. Memory address of storable arrays are fixed, so you can pass them to C routines. The pointer to the array contents is obtained by 'withStorableArray'. The idea is similar to 'ForeignPtr' (used internally here). The pointer should be used only during execution of the 'IO' action retured by the function passed as argument to 'withStorableArray'. {-# OPTIONS_GHC -fglasgow-exts #-} import Data.Array.Storable import Foreign.Ptr import Foreign.C.Types main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int) readArray arr 1 >>= print withStorableArray arr $ \ptr -> memset ptr 0 40 readArray arr 1 >>= print foreign import ccall unsafe "string.h" memset :: Ptr a -> CInt -> CSize -> IO () If you want to use this pointer afterwards, ensure that you call 'touchStorableArray' AFTER the last use of the pointer, so that the array will be not freed too early. > The Haskell Array Preprocessor (STPP) Using in Haskell mutable arrays (IO and ST ones) is not very handy. But there is one tool which adds syntax sugar and makes using of such arrays very close to that in imperative languages. It is written by Hal Daume III and you can get it as http://www.isi.edu/~hdaume/STPP/stpp.tar.gz Using this tool, you can index array elements in arbitrary complex expressions with just "arr[|i|]" notation and this preprocessor will automatically convert such syntax forms to appropriate calls to 'readArray' and 'writeArray'. Multi-dimensional arrays are also supported, with indexing in the form "arr[|i|][|j|]". See further descriptions at http://www.isi.edu/~hdaume/STPP/ > Unsafe indexing, freezing/thawing, running over array elements > GHC-specific topics: > Parallel arrays (module GHC.PArr) > Welcome to machine: Array#, MutableArray#, ByteArray#, MutableByteArray# notes for contributors to this page: if you have any questions, please ask at the IRC/maillist. if you have any answers, please submit them directly to this page. please don't sign your contributions, so that anyone will feel free to further improve this page. but if you are compiler/Array libraries author - please sign your text to let us know that it is the Last Word of Truth :-) -- Best regards, Bulat mailto:bulatz@HotPOP.com

1 0

Haskell Weekly News: January 9, 2006
by dons＠cse.unsw.edu.au 08 Jan '06

08 Jan '06

Haskell Weekly News: January 9, 2006 Greetings, and thanks for reading the 19th issue of HWN, a weekly newsletter for the Haskell community. Each Monday, new editions are posted to [1]the Haskell mailing list and to [2]The Haskell Sequence. [3]RSS is also available. 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ 3. http://sequence.complete.org/node/feed New Releases * A Faster Binary. Bulat Ziganshin [4]posted a preliminary optimised Binary library, achieving excellent (de)serialization speeds of around 50 Mb/s in testing. 4. http://article.gmane.org/gmane.comp.lang.haskell.cafe/10803 Resources and Tools * Haskell mail. Simon Peyton-Jones has [5]put together a [6]complete archive of the Haskell mailing list since its birth in Sept 1990 until Oct 2000 -- the date where the [7]current mailman archive takes over. This is a valuable resource for the community. 5. http://article.gmane.org/gmane.comp.lang.haskell.general/12948 6. http://research.microsoft.com/%7Esimonpj/haskell/haskell-email-11Sep1990-27… 7. http://www.haskell.org//pipermail/haskell/ * haskell.org. John Peterson is [8]seeking comments on the haskell.org move to MediaWiki. Currently only the [9]front page is finished, and its time for comments. In the end this will allow anyone to come in and fix up the main haskell.org pages - the people, the projects, the help for beginners, all of it. One job that will be needed is to move the current hawiki contents onto MediaWiki. Feel free to start adding stuff to the new haskellwiki. 8. http://article.gmane.org/gmane.comp.lang.haskell.general/12981 9. http://haskell.org/haskellwiki/Haskell Discussion * Language Shootout. [10]Discussion took place on on haskell-cafe to improve the performance of the Haskell entries. This process has greatly improved some entries. Haskell is now [11]the fastest entry for the concurrency benchmark, Chameneos. More can still be done. Some entries are being worked on [12]here. The problems are quite short, and fairly easy to solve, so fire up the profiler and hack! 10. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/10663 11. http://shootout.alioth.debian.org/benchmark.php?test=chameneos&lang=all 12. http://haskell.org/hawiki/ShootoutEntry * MonadZero. Cale Gibbard [13]opened a discussion about reinclusion of MonadZero, and removal of `fail' from the Monad class, citing the overuse of monadic typing to indicate the possibility of failure as one of the problems. Instead, MonadZero should be used for failure. [14]References were made to the discussions that took place on this issue during the Haskell 98 process. 13. http://thread.gmane.org/gmane.comp.lang.haskell.general/12930 14. http://www.cs.chalmers.se/~rjmh/Haskell/Messages/Decision.cgi?id=2 * History channel. On a similar theme, an expedition took place on #haskell into functions and classes from earlier implementations of Haskell that had disappeared by Haskell 98. Of particular interest was the Eval class, and various things in the [15]constructor class prelude from Gofer, such as: class (Functor f, Functor g) => NatTransf f g where eta :: f a -> g a and fun definitions like: undefined :: a undefined | False = undefined 15. http://www.cse.unsw.edu.au/~dons/cc.prelude Darcs Corner A darcs gui. Eric Kow [16]proposed resurrecting the darcs wxhaskell gui for a new darcs gui. 16. http://thread.gmane.org/gmane.comp.version-control.darcs.user/9189 Quote of the Week * autrijus stares at type Eval x = forall r. ContT r (ReaderT x IO) (ReaderT x IO x) and feels very lost <shapr> Didn't you write that code? <autrijus> yeah. and it works <autrijus> I just don't know what it means. Contributing to HWN You can help us create new editions of this newsletter. Please see the [17]contributing information, send stories to dons -at- cse.unsw.edu.au. The Darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 17. http://sequence.complete.org/hwn-contrib

1 0

Parsing bug in GHC 6.4.1 ?
by Bruno Oliveira 08 Jan '06

08 Jan '06

Hello, The following class definition: > class Foo o where > (:+) :: o -> o -> o and even the following function definition: > bar f (x,y) = x :+ y are accepted by GHC. However, when I try to create one instance of Foo: > instance Foo Int where > x :+ y = x + y I get the following error message: Parsing.lhs:7:5: Pattern bindings (except simple variables) not allowed in instance declarations x :+ y = x + y The same error still occurs if I change the infix operator to be (:+:). However, if I define: > class Foo3 o where > (<+>) :: o -> o -> o > instance Foo3 Int where > x <+> y = x + y Everything works as expected. The only explanation that I have is that this is a (parsing) bug in GHC... This is probably related to the fact that > (:+) :: Int -> Int -> Int > f :+ g = f + g is an invalid definition (it complains that ":+" is not a data constructor). I have not tried this code in other Haskell compiler (like Hugs) or even previous versions of GHC. I would be interested to know how do those behave. Cheers, Bruno

3 4

A collection of related proposals regarding monads
by Cale Gibbard 08 Jan '06

08 Jan '06

I personally feel that the inclusion of 'fail' in the Monad class is an ugly solution to the problem of pattern matching, and gives the incorrect impression that monads should have some builtin notion of failure. Indeed, it's becoming common to type the result of some function in an arbitrary monad in order to indicate the potential for failure, which is strictly speaking, not the right thing to do. (In a lot of cases, it's going to be no better than complete program failure) We ought to be using MonadZero when we want to express failure, but it's gone! What do people think of the following proposal? Remove fail from the Monad class. Reinstate MonadZero as a separate class as in Haskell 1.4. Do notation is translated as in Haskell 1.4: do {e} = e do {e;stmts} = e >> do {stmts} -- if p is refutable, do {p <- e; stmts} = let ok p = do {stmts}; ok _ = mzero in e >>= ok -- if p is irrefutable, do {p <- e; stmts} = e >>= \p -> do {stmts} do {let decls; stmts} = let decls in do {stmts} Thus, refutable pattern matches occuring in a do-expression would force the expression to be typed explicitly with MonadZero. This is probably a good thing, as it forces one to think about the consequences of not properly dealing with a pattern match in any monad which doesn't explicitly allow for failure. Even if this translation of do-syntax isn't accepted, I still think that we should have a separate MonadZero. Its existence lets various type signatures become more expressive. There are a lot of cases where a MonadPlus constraint pops up where a MonadZero constraint would do. (I've also been seeing Monad get used for these cases, when it shouldn't!) This distinction allows one to see immediately when a monad is getting used for failure or whether choice is really essential. I'd also like to see the current use of MonadPlus split into MonadElse (or MonadOr) and MonadPlus, as described at the bottom of http://www.haskell.org/hawiki/MonadPlus as it helps to clarify the distinction between backtracking-type failure and immediate failure in types. We could even put this distinction to good use in many monads which do support backtracking anyway: instance MonadElse [] where [] `morelse` ys = ys (x:xs) `morelse` ys = (x:xs) Lastly, it would be nice to have some standard name for the function: option :: (MonadPlus m) => [a] -> m a option = foldr (mplus . return) mzero which seems to come up quite a bit in my experience with nondet monads. - Cale P.S. Oh, and don't get me started about the whole Functor subclass thing, and the inclusion of join in the Monad class. Of course I want those too. :) P.P.S. This reopens the possibility for monad comprehensions, and the more general versions of filter, concat, etc. in the 1.4 prelude -- I wasn't actually around for Haskell 1.4, but I *really* think they'd be a nice language feature to have, as I like to view monads as an abstraction of *containers*, which that syntax/methodology emphasises. I usually find that initially teaching monads to newcomers in terms of containers is much more effective, and that syntax would allow for a nice segue from lists to monads. If people think the error messages are scary, we could provide a switch -fbeginner and a more 98-like prelude to turn monad comprehensions and any other potentially scary features off for the newcomers.

6 9

MPC 2006 2nd Call for Papers
by Tarmo Uustalu 07 Jan '06

07 Jan '06

NEWS: - Invited speakers: Robin Cockett, University of Calgary Olivier Danvy, Aarhus Universitet Oege de Moor, University of Oxford - The paper submission system is open. - Two satellite workshops: Constructive Methods for Parallel Programming, CMPP Mathematically Structured Functional Programming, MSFP SECOND CALL FOR PAPERS 8th International Conference on Mathematics of Program Construction MPC '06 Kuressaare, Estonia, 3-5 July 2006 http://cs.ioc.ee/mpc-amast06/mpc/ colocated with AMAST '06 Background The biennial MPC conferences aim to promote the development of mathematical principles and techniques that are demonstrably useful and usable in the process of constructing computer programs. Topics of interest range from algorithmics to support for program construction in programming languages and systems. The previous conferences were held in Twente, The Netherlands (1989), Oxford, UK (1992), Kloster Irsee, Germany (1995), Marstrand, Sweden (1998), Ponte de Lima, Portugal (2000), Dagstuhl, Germany (2002) and Stirling, UK (2004, colocated with AMAST '04). The 2006 conference will be held at Kuressaare, Estonia, colocated with AMAST '06. Invited speakers Robin Cockett, University of Calgary Olivier Danvy, Aarhus Universitet Oege de Moor, University of Oxford Important dates * Submission of abstracts: 27 January 2006 * Submission of full papers: 3 February 2006 * Notification of authors: 17 March 2006 * Camera-ready version: 14 April 2006 Topics Papers are solicited on mathematical methods and tools put to use in program construction. Topics of interest range from algorithmics to support for program construction in programming languages and systems. Some typical areas are type systems, program analysis and transformation, programming language semantics, program logics. Theoretical contributions are welcome provided their relevance for program construction is clear. Reports on applications are welcome provided their mathematical basis is evident. Submission and publication Submission is in two stages. Abstracts (plain text) must be submitted by 27 January 2006. Full papers (pdf) adhering to the llncs style must be submitted by 3 February 2006. There is no official page limit, but authors should strive for brevity. The web-based submission system is open. Papers must report previously unpublished work and not be submitted concurrently to another conference with refereed proceedings. PC members may submit. Accepted papers must be presented at the conference by one of the authors. The proceedings of MPC '06 will be published in the Lecture Notes in Computer Science series of Springer-Verlag. After the conference, the authors of the best papers will be invited to submit revised versions to a special issue of the Science of Computer Programming journal of Elsevier. Programme committee Tarmo Uustalu, Institute of Cybernetics, Tallinn (chair) Roland Backhouse, University of Nottingham Eerke Boiten, University of Kent Venanzio Capretta, University of Ottawa Sharon Curtis, Oxford Brookes University Jules Desharnais, Université de Laval Jeremy Gibbons, University of Oxford Lindsay Groves, Victoria University of Wellington Ian Hayes, University of Queensland William Harrison, University of Missouri Johan Jeuring, Universiteit Utrecht Dexter Kozen, Cornell University Christian Lengauer, Universität Passau Lambert Meertens, Kestrel Institute Bernhard Möller, Universität Augsburg Shin-Cheng Mu, University of Tokyo José Oliveira, Universidade do Minho Alberto Pardo, Universidad de la República Ross Paterson, City University London Ingrid Rewitzky, University of of Stellenbosch Varmo Vene, University of Tartu Satellite workshops Two workshops will be held in conjunction with MPC 2006 as satellites on 2 July 2006: 5th International Workshop on Constructive Methods for Parallel Programming, CMPP 2006 Workshop on Mathematically Structured Functional Programming, MSFP 2006 Venue Kuressaare (pop. 16000) is the main town on Saaremaa, the second-largest island of the Baltic Sea. Kuressaare is a charming seaside resort on the shores of the Gulf of Riga highly popular with Estonians as well as visitors to Estonia. The scientific sessions of MPC/AMAST 2006 will take place at Saaremaa Spa Hotel Meri, one among the several new spa hotels in the town. The social events will involve a number of sites, including the 14th-century episcopal castle. Accommodation will be at Saaremaa Spa Hotels Meri and Rüütli. To get to Kuressaare and away, one must pass through Tallinn (pop. 402000), Estonia's capital city. Tallinn is famous for its picturesque medieval Old Town, inscribed on UNESCO's World Heritage List. Local organizers MPC/AMAST 2006 is organized by Institute of Cybernetics, a research institute of Tallinn University of Technology. The local organizers are Tarmo Uustalu (chair), Monika Perkmann, Juhan Ernits, Ando Saabas, Olha Shkaravska, Kristi Uustalu. Contact email address: mpc06(at)cs.ioc.ee.

1 0

(small) records proposal for Haskell '06
by David Roundy 06 Jan '06

06 Jan '06

Hi all, I'd like to humbly submit a conservative proposal for changes to the records mechanism for Haskell '06. The plan for Haskell '06 (to the extent that there is one) is to make it a conservative modification of Haskell 98, which is a good idea. As such, I don't think features should be added to the language that haven't been both implemented and tested, and the problem with the whole records problem is that pretty much every proposed improvement is *not* backwards-compatible with Haskell 98, and therefore hasn't been either implemented or tried out. My idea is to make a small change, which will also not be backwards-compatible with Haskell 98, but will *almost* be, and will be hopefully forward-compatible with most complete solutions. At a minimum, the proposed change will allow the prototyping of real solutions as a non-invasive preprocessor a la DrIFT. My proposal is simply to remove the automatic declaration of accessor functions. In Haskell 98, data FooBar = Foo { foo :: Int } | FooBar = { foo :: Int, bar :: Int } desugars to something like data FooBar = Foo Int | FooBar Int Int foo :: FooBar -> Int foo (Foo f) = f foo (FooBar f _) = f bar :: FooBar -> Int bar (Foo _) = error "bad Foo" bar (FooBar _ b) = b plus additional sugar for constructors and pattern matching. I would leave the sugar for constructors and pattern matching in place, but remove the automatic declaration of functions "foo" and "bar". This change "solves" the problem that different records in a single namespace cannot share field names in a simple manner. In order to allow the writing of records code with is both valid Haskell 98 and valid Haskell '06, I'd suggest a pragma that causes the Haskell '06 compiler to generate the accessor functions. It's a bit ugly, but seems best to me. An alternative would be a standard TH function to do the same, but I don't know if TH is going to be included in Haskell '06. This change may look like a step backwards (which it is), but I think that it would allow significant steps forward. One open question (in my mind) would be whether we'd allow data Foo = FooInt { foo :: Int } | FooChar { foo :: Char } In the "new" system, there's no reason this need be illegal. -- David Roundy http://www.darcs.net

11 23

Re: [Haskell] GHC and GLUT
by Wolfgang Jeltsch 06 Jan '06

06 Jan '06

Am Freitag, 6. Januar 2006 21:24 schrieb Mark T.B. Carroll: > Does installing the libsm-dev package help? > > -- Mark Thank you, Mark and Jared. Installing the libsm-dev package resulted in ld outputting a similar error message for -lXmu. After also installing libxmu-dev, linking was possible. Are libsm-dev and/or libxmu-dev needed for every Haskell GLUT application or just for certain examples? If they are always needed, some package has not declared all its dependencies. In this case, which package is the one with the dependency declaration bug? Best wishes, Wolfgang

3 3

GHC and GLUT
by Wolfgang Jeltsch 06 Jan '06

06 Jan '06

Hello, I just wanted to compile the Gears example from the HOpenGL's GLUT source but it didn't work. I got the following messages: Chasing modules from: Gears.hs Compiling Main ( Gears.hs, Gears.o ) Linking ... /usr/bin/ld: cannot find -lSM collect2: ld returned 1 exit status I use Debian GNU/Linux 3.1 (sarge) and have the following packages installed: ghc6 (6.2.2-3) ghc6-hopengl (6.2.2-3) ghc6-prof (6.2.2-3) Anyone who can help me? Best wishes, Wolfgang

2 3

Re: [Haskell] A collection of related proposals regarding monads
by Cale Gibbard 05 Jan '06

05 Jan '06

On 05/01/06, David Menendez <zednenem(a)psualum.com> wrote: > Cale Gibbard writes: > > > I personally feel that the inclusion of 'fail' in the Monad class is > > an ugly solution to the problem of pattern matching, and gives the > > incorrect impression that monads should have some builtin notion of > > failure. Indeed, it's becoming common to type the result of some > > function in an arbitrary monad in order to indicate the potential for > > failure, which is strictly speaking, not the right thing to do. (In a > > lot of cases, it's going to be no better than complete program > > failure) > > > > We ought to be using MonadZero when we want to express failure, but > > it's gone! > > Yeah, I don't like fail either. In fact, I usually forget to define it, > even for instances of MonadPlus. > > There are typically three ways to indicate error in existing monad > libraries, e.g., > > mzero :: MonadPlus m => m a > fail :: Monad m => String -> m a > throwError :: MonadError e m => e -> m a > > I would say that fail and throwError essentially have the same meaning, > but I distinguish them from mzero. To my mind, 'mzero' means "no > answer", whereas fail and throwError mean "something's wrong". > > For example, my implementation of Nondet doesn't backtrack over errors: > > mzero `mplus` m = m > throwError e `mplus` m = throwError e > > Should a pattern match failure call mzero or throwError? I was > originally going to say throwError, but now I'm not so sure. First, > MonadError is severely non-H98 (fundeps). Second, we would either need > the error type to belong to some class which includes pattern match > failures, or have a dedicated throwPatternMatchFailure method in > MonadError. Finally, you can write sensible code which backtracks on > pattern-match failure, e.g., > > do ... > Just a <- lookup ... > ... > > > Even if this translation of do-syntax isn't accepted, I still think > > that we should have a separate MonadZero. > > I like the idea of a separate MonadZero. Do we know why it was combined > with MonadPlus? Were there efficiency concerns, or did people dislike > having to declare all those separate instances? > > > I'd also like to see the current use of MonadPlus split into MonadElse > > (or MonadOr) and MonadPlus, as described at the bottom of > > http://www.haskell.org/hawiki/MonadPlus > > as it helps to clarify the distinction between backtracking-type > > failure and immediate failure in types. We could even put this > > distinction to good use in many monads which do support backtracking > > anyway: > > > > instance MonadElse [] where > > [] `morelse` ys = ys > > (x:xs) `morelse` ys = (x:xs) > > With backtracking monads, you can use Oleg's msplit operator to get > morelse, soft-cut, and various other operations. > > class MonadPlus m => MonadChoice m where > msplit :: m a -> m (Maybe (a, m a)) > > mif :: MonadSplit m => m a -> (a -> m b) -> m b -> m b > mif p t e = msplit p >>= maybe e (\(x,xs) -> t x `mplus` (xs >>= t)) > > a `orElse` b = mif a return b > > With non-backtracking monads, you can use throwError or just use mplus > and remind people that non-backtracking monads don't backtrack. My main concern is that mplus means fairly different things in different monads -- it would be good to be able to expect instances of MonadPlus to satisfy monoid, left zero, and left distribution laws, and instances of MonadElse to satisfy monoid, left zero and left catch. It's just good to know what kinds of transformations you can do to a piece of code which is meant to be generic. > > > Lastly, it would be nice to have some standard name for the function: > > option :: (MonadPlus m) => [a] -> m a > > option = foldr (mplus . return) mzero > > which seems to come up quite a bit in my experience with nondet > > monads. > > Mine too. Someone else mentioned "choose", which seems nice. Or, > "fromList". > > Incidentally, would GHC optimize "msum (map return xs)" to "foldr (mplus > . return) mzero xs"? > > > P.S. Oh, and don't get me started about the whole Functor subclass > > thing, and the inclusion of join in the Monad class. Of course I want > > those too. :) > > For the recond, my ideal hierarchy would look something like this: > > class Functor f where > map :: (a -> b) -> f a -> f b > > class Functor f => Applicative f where > return :: a -> f a > ap :: f (a -> b) -> f a -> f b > lift2 :: (a -> b -> c) -> f a -> f b -> f c > > ap = lift2 ($) > lift2 f a b = map f a `ap` b > > class Applicative m => Monad m where > join :: m (m a) -> m a > (>>=) :: m a -> (a -> m b) -> m b > > join m = m >>= id > m >>= f = join (map f m) > > class Monad m => MonadZero m where > nothing :: m a > > class MonadZero m => MonadPlus m where > (++) :: m a -> m a -> m a > > class MonadPlus m => MonadChoice m where > msplit :: m a -> m (Maybe (a, m a)) > > I guess you could put "return" in its own class, PointedFunctor, between > Functor and Applicative, but I haven't seen a reason to. Even without > that, it's probably excessive. Well, me too :) Of course, this sort of thing (especially with the inclusion of PointedFunctor and Applicative) brings us back to wanting something along the lines of John Meacham's class alias proposal. I remember there was a lot of commotion about that and people arguing about concrete syntax. Was any kind of consensus reached? Do we like it? How does it fare on this hierarchy? I think we need some provision for simplifying instance declarations in this kind of situation. It seems to be a common scenario that you have some finely graded class hierarchy, and you really want to be able to declare default instances for superclasses based on instances for subclasses in order to not force everyone to type out a large number of class instances. Another idea I've had for this, though I haven't really thought all of the consequences out, (and I'm looking forward to hearing about all the awful interactions with the module system) is to allow for default instances somewhat like default methods, together with potentially a little extra syntax to delegate responsibility for methods in default instances. The start of your hierarchy could look something like: ---- class Functor f where map :: (a -> b) -> f a -> f b class Functor f => PointedFunctor f where return :: a -> f a instance Functor f where require map -- this explicitly allows PointedFunctor instances to define map class PointedFunctor f => Applicative f where ap :: f (a -> b) -> f a -> f b lift2 :: (a -> b -> c) -> f a -> f b -> f c ap = lift2 ($) lift2 f a b = map f a `ap` b instance Functor f where require map instance PointedFunctor f => Functor f where map = ap . return instance PointedFunctor f where require return class Applicative m => Monad m where join :: m (m a) -> m a (>>=) :: m a -> (a -> m b) -> m b join m = m >>= id m >>= f = join (map f m) instance Functor m where require map instance PointedFunctor m where require return map f x = x >>= (return . f) instance PointedFunctor m => Applicative m where ap fs xs = do f <- fs x <- xs return (f x) ---- This is a little verbose, but the intent is to have classes explicitly declare what default instances they allow, and what extra function declarations they'll need in an instance to achieve them. Here I used 'require' for this purpose. To be clear, in order to define an instance of Monad with the above code, along with all its superclasses, we could simply define return and (>>=) as we would in Haskell 98. Since a definition of return is then available, an instance of PointedFunctor would be inferred, with the default instance providing an implementation of map which satisfies the requirement for the default Functor instance for PointedFunctor. We then get a default implementation of Applicative for free due to the instance of PointedFunctor which we've been able to construct. An alternate route here would be to just define return, map, and join. The declaration for map leads to an instance of Functor. The default instance of PointedFunctor requiring return is used, but the default implementation of map there is ignored since the user has already provided an explicit implementation of map. Bind is defined by the default method provided using join and map, then an instance of Applicative is constructed using bind and return. Some things to note: * The goal should always be to take implementations as early as they become available, that is, if the user provides something it's taken first, then each subclass gets a shot at it starting with the bottom-most classes in the partial order and working up. We'll likely run into problems with multiple inheritance, but I think that simply reporting an error of conflicting instance declarations when two incomparable default instances would otherwise be available is good enough. Such situations are rare, and the user will always be able to simply provide their own instance and resolve ambiguities. * Class constraints on classes (like the Applicative constraint on the Monad class above) are used to deny instances only after it's been determined what instances are really available via defaulting. Since the class definition for Monad provides a default instance for Applicative, the user can avoid the trouble of declaring one, provided that an instance for PointedFunctor can be constructed. * What extra methods might be needed, and what defaults are available are specified directly in the classes, rather than simply allowing any instance to come along and mess with the class hierarchy by providing implementations of arbitrary superclass methods. - Cale

2 2

monads, records, verbosity
by S. Alexander Jacobson 05 Jan '06

05 Jan '06

Much of the discussion here recently has been related to debate about complexifying the monad hierarchy. The fact that Haskell record syntax is abysmal and the verbosity of various possible solutions. They appear to interrelate. Would it be possible/reasonable to get rid of data, class, and instance declarations and rely on type inference for everything? Here is my strawman version: * functions definitions imply the data declarations required foo True = Just "abc" foo False = Nothing ==implies==> data A1 = True | False data A2 a = Just a | Nothing * all function definitions are actually instance declarations of an implicit class that implements that function so e.g. foo True = Just "abc" foo False = Nothing ==implies==> class Foo a b where foo::a->b instance Foo A1 A2 where foo True = Just "abc" foo False = Nothing * multiple definitions of the same function imply distinct instance declarations: foo 0 = Nothing foo x = Just (x+1) ==implies ==> class Foo a b where foo::a->b -- same as above definition of Foo instance Foo A1 (A2 A1) where ..... * field labels happen in context mkPot = Pot {profit=0,amounts=[]} updatePot p = p {profit \= (1+),amount \= (1:)} getProfit p = profit p == implies ==> data A3 = Pot Int [Int] class Profit a where profit::a->Int class Amounts a where amounts::a->[Int] instance Profit A3 where profit (Pot a _)=a instance Amounts A3 where amounts (Pot _ a)=a class UpdatePot a where updatePot::a->a instance UpdatePot A3 where updatePot (Pot a b) = Pot (1+a) (1:b) getProfit p = profit p * default instances are as follows foo a b c = b -- the default instance foo (a::Pot) b c = c -- the specialized instance Is this possible/reasonable? -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

2 1