April 2002 - Haskell - Haskell.org

Matrix library in Haskell
by Jan Kybic 23 Apr '02

23 Apr '02

Hello, I am just discovering Haskell, so sorry if this is not the right place to ask. I want to use it for some numerical calculations. I need something higher level than C++ and faster than Python or Matlab and from the initial experiments it seems that Haskell could be the right choice. My question is: Is there any matrix/vector library available with common operations (dot products, matrix products, linear system solution etc.) ? I could not find any. I am including her my first try on such a library, in case it might be useful for somebody. However, I am not perfectly happy with the design. In particular I would like to define MatrixClass and VectorClass so that applying a getRow operation on a matrix instance would yield automatically the correct instance of the VectorClass, but I do not know how to express this interdependency, so for the moment I have dropped the classes. Yours, Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic(a)ieee.org> Robotvis, INRIA, Sophia-Antipolis, France or <Jan.Kybic(a)sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/ -- Module implementing vectors, matrices, and operations on them -- it uses the multiparameter class extension -- -- $Id: LinearAlgebra.hs,v 1.4 2002/04/22 11:44:41 jkybic Exp $ -- Jan Kybic, April 2002 module LinearAlgebra where import Array import Complex import Observe -------------------------------------------------------------------- -- now define the concrete vector and array implementations -- TODO: This could be accelerated using IArray/ UArray -- TODO: Make it a proper instance of Show newtype ArrayVectorType a = ArrayVector (Array Int a) deriving Show newtype ArrayMatrixType a = ArrayMatrix (Array (Int,Int) a) deriving Show listToVec l = ArrayVector (array (0,uplim) $ zip [0..uplim] l) where uplim = (length l) -1 vecToList (ArrayVector v) = [ v!i | i <- indices v ] dot (ArrayVector a) (ArrayVector b) = sum [ a!i * b!i | i <- indices a ] norm2 a = dot a a norm a = sqrt (norm2 a) (!@) (ArrayVector v) i = v!i sizeV (ArrayVector v) = rangeSize $ bounds v indicesV v= [0..(sizeV v - 1)] scaleV (ArrayVector a) s = ArrayVector ( fmap (\x -> s * x) a ) (+@) a b = listToVec [ a!@i + b!@i | i <- indicesV a ] (-@) a b = listToVec [ a!@i - b!@i | i <- indicesV a ] -- matrix operations (!@@) (ArrayMatrix m) (i,j) = m!(i,j) listToMat l = let { bnds=((0,0),(m,n)) ; m=length l -1 ; n= length (head l) -1} in ArrayMatrix ( array bnds [ ((i,j),(l!!i)!!j) | (i,j) <- range bnds ] ) matToList a = [ [ a !@@ (i,j) | j <- range $ cbounds a ] | i <- range $ rbounds a ] boundsM (ArrayMatrix a) = bounds a rbounds m = let z=boundsM m in (fst(fst z),fst(snd z)) cbounds m = let z=boundsM m in (snd(fst z),snd(snd z)) nrows = rangeSize . rbounds ncols = rangeSize . cbounds getRow a i = -- extract row i as vector listToVec [ a!@@(i,j) | j <- range $ cbounds a ] getCol a j = -- extract column j as vector listToVec [ a!@@(i,j) | i <- range $ cbounds a ] showMat a = "[ " ++ concat [ showVec (getRow a i) ++ " " | i <- range (rbounds a) ] ++ "]" scaleMat (ArrayMatrix a) s = ArrayMatrix ( fmap (\x -> s * x) a ) matMult a b = let bnds = transTup (rbounds a,cbounds b) in ArrayMatrix (array bnds [ ((i,j), (getRow a i) `dot` getCol b j) | (i,j) <- range bnds ]) idMat n = -- create an identity matrix let bnds=((0,0),(n-1,n-1)) in ArrayMatrix (accumArray (+) 0.0 bnds [ ((i,i),1.0) | i <- [0..n-1] ]) -- cross takes two vectors of length three and calculates their cross product -- uncomment the run-time checks if you prefer safety over speed -- the signature is a little limiting to avoid uncertainity of the resulting -- vector cross a b -- | or [ sizeV a /=3 , sizeV b /=3 ] = -- error "Cross product needs length 3 vectors" -- | otherwise = listToVec [ a !@ 1 * b !@ 2 - a !@ 2 * b !@ 1, - a !@ 0 * b !@ 2 + a !@ 2 * b !@ 0, a !@ 0 * b !@ 1 - a !@ 1 * b !@ 0 ] vangle a b = acos (cosvangle a b) -- angle between two vectors cosvangle' a b = -- the cos of an angle between two vectors let mag= sqrt ( norm2 a * norm2 b ) in if mag>0.0 then (dot a b)/mag else 0.0 -- the above version had numerical problems cosvangle a b = max ( min (cosvangle' a b) 1.0 ) (-1.0) showVec a = -- converts a vector to a string "[ " ++ concat [ show (a !@ i) ++ " " | i <- [0..sizeV a-1] ] ++ "]" subvector a (i,j) = -- another vector with indices i..j listToVec [ a !@ k | k <- [i..j] ] transTup ((a,b),(c,d)) = ((a,c),(b,d)) -- transpose a tuple of tuples -- type synonymes type DoubleVector = ArrayVectorType Double type DoubleMatrix = ArrayMatrixType Double -- Observable instance instance (Observable a) => Observable (ArrayVectorType a) where observer (ArrayVector a) = send "ArrayVector" (return ArrayVector << a) instance (Observable a) => Observable (ArrayMatrixType a) where observer (ArrayMatrix a) = send "ArrayMatrix" (return ArrayMatrix << a) -- Functor instance instance Functor ArrayVectorType where fmap f (ArrayVector a) = ArrayVector ( fmap f a ) -- end of Linear Algebra.hs

2 1

defining (-> Bool) as a set
by Hal Daume III 23 Apr '02

23 Apr '02

I'd like to be able to define something like instance Eq a => Coll (-> Bool) a where empty = \_ -> False single x = \y -> if x == y then True else False union a b = \x -> a x || b x insert s x = \y -> x == y || s y and the like However, this seems to be impossible. Is this the type lambda restriction that's been discussed recently on the mailing list? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

4 6

style questino: where to put instances
by Hal Daume III 23 Apr '02

23 Apr '02

I know you're all probably pretty tired of hearing from me, but I have a style question. Let's say I'm defining a hashmap. I have a module HashMap which defines a class Hashable a where hash :: a -> Int or something like that. I have a common datastructure called a Foo which I want to be able to hash. Foo and a bunch of accompanying functions are defined in module Foo. Where should I put the instance Hashable Foo? (1) In Foo.hs pros : seems somewhat appropriate since it's basically defining a function on Foo and if I don't export the constructors for Foo, this is the only place it can go cons : means i have to import HashMap into Foo even though I'm not actually using a HashMap. Sure I can only import the part I need. (2) In HashMap.hs pros : when you import HashMap you get all necessary instances cons : Foo is application specific, HashMap is not; reduces reusability <-- I don't like option (2) (3) In Instances.hs -- i.e., create a new file for instances pros : modular cons : what if FOo doesn't export constructors? requires importing lots of files which often slows down compilation since a change to one things means *everything* has to recompile (4) something I haven't thought of I know edison tends to follow (3); in general I follow (1), but sometimes I run in to problems of mutually dependant modules this way. How do people resolve this problem? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

SAS'02 CFP Reminder -- Submission Deadline May 5, 2002
by SAS2002 23 Apr '02

23 Apr '02

(Apologies for multiple postings) ---------------------------------------------------------------------- CALL FOR PAPERS (SAS'02) The 9th International Static Analysis Symposium September 17 - 20 2002, Madrid, Spain http://clip.dia.fi.upm.es/SAS02 Submission deadline: May 5, 2002 ---------------------------------------------------------------------- Static Analysis is increasingly recognized as a fundamental tool for high performance implementations and verification systems of high-level programming languages. The series of Static Analysis Symposia has served as the primary venue for presentation of theoretical, practical, and application advances in the area. The Ninth International Static Analysis Symposium (SAS'02) will be held at the Technical University of Madrid, co-located with Logic-based Program Development and Transformation (LOPSTR'02) and the APPIA-GULP-PRODE Joint Conference on Declarative Programming (AGP'02). Previous symposia were held in Paris, Santa Barbara, Venice, Pisa, Paris, Aachen, Glasgow and Namur. The technical program for SAS'02 will consist of invited lectures, tutorials, panels, presentations of refereed papers, and software demonstrations. Contributions are welcome on all aspects of Static Analysis, including, but not limited to: * abstract interpretation, * data flow analysis, * verification systems, * program specialization, * abstract domains, * optimizing compilers, * theoretical frameworks, * type inference, * abstract model checking, * complexity analysis, * abstract testing, * security analysis. Submissions can address any programming paradigm, including concurrent, constraint, functional, imperative, logic and object-oriented programming. Survey papers that present some aspect of the above topics with a new coherence are also welcome. Papers must describe original work, be written and presented in English, and must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal or a conference with refereed proceedings. Submission Instructions ----------------------- All submissions must be performed electronically at http://clip.dia.fi.upm.es/SAS02/submission.html. Submitted papers should be at most 15 pages excluding bibliography and well-marked appendices. Program committee members are not required to read the appendices, and thus papers should be intelligible without them. The proceedings will be published by Springer-Verlag in the Lecture Notes in Computer Science series (see http://www.springer.de/comp/lncs/authors.html for the LNCS author instructions). Thus, adhering to that style already in the submission is strongly encouraged. Papers should be submitted either in PostScript or PDF format and they should be interpretable by Ghostscript or Acrobat Reader. Papers must be printable on either A4 paper or US letter, and preferably on both. Important Dates --------------- May 5, 2002 Submission deadline June 10, 2002 Notification June 30, 2002 Final version Sept 17-20, 2002 SAS'02 Program Committee ----------------- Manuel Hermenegildo (Chair) Technical University of Madrid, Spain German Puebla (Co-chair) Technical University of Madrid, Spain Radhia Cousot Ecole Polytechnique, France Saumya Debray The University of Arizona, USA Manuel Fahndrich Microsoft Research, USA Roberto Giacobazzi Univerity of Verona, Italy Chris Hankin Imperial College, UK Giorgio Levi Univerity of Pisa, Italy Kim Marriott Monash University, Australia Alan Mycroft Cambridge University, United Kingdom Ganesan Ramalingam IBM T.J. Watson Research Center, USA Martin Rinard Massachusetts Institute of Technology, USA Shmuel Sagiv Tel-Aviv Univerisity, Israel Reinhard Wilhelm Universitat des Saarlandes, Germany Contact Info ------------ Email: sas02(a)clip.dia.fi.upm.es Fax: + 34 91 352 4819 Phone: + 34 91 336 7448 Post: Manuel Hermenegildo (Ref.: SAS'02) Facultad de Informatica Universidad Politecnica de Madrid 28660 Boadilla del Monte Madrid, Spain ----------------------------------------------------------------------

1 0

RE: semi-private exports
by Simon Marlow 23 Apr '02

23 Apr '02

> In my NLP.Prelude file, I define: > > > newtype Token = Token [Word8] > > and I export only the type, not the constructor because I > don't users of > my package to be able to inspect/modify the list directly. > However, in my > NLP.IO module, in which I define IO for some of my data > types, I need to > be able to access it directly. > > In Java/C#, I would make Token public and the constructor > protected (i.e., > public for the current package but private for other people). I would > really like to be able to do something similar. Any ideas? Define the type in a private module, say DLP.Prelude.Private, which is used by NLP.IO, and re-export it abstractly from NLP.Prelude. You don't get the benefit of language support for enforcing that NLP.Prelude.Private isn't nefariously imported by the client, but at least now with hierarchical modules the private module name isn't polluting the client's module namespace. Cheers, Simon

1 0

RDP'03 - First announcement
by Salvador Lucas Alba 23 Apr '02

23 Apr '02

[Apologies for multiple copies of this announcement] ************************************************************************** ************************* First announcement *************************** ************************************************************************** Federated Conference on Rewriting, Deduction and Programming (RDP) http://www.dsic.upv.es/~rdp03 Valencia, Spain, June 8 - 14, 2003 -------------------------------------------------------------------------- We are pleased to announce the Federated Conference on Rewriting, Deduction and Programming (RDP) to be held in Valencia, Spain, in June 2003. The conference will be hosted by the Departamento de Sistemas Informaticos y Computacion (DSIC) at the Universidad Politecnica de Valencia. PARTICIPANTS 14th Int. Conference on Rewriting Techniques and Applications, RTA'03 6th Int. Conference on Typed Lambda Calculi and Applications, TLCA'03 4th Int. Workshop on First Order Theorem Proving, FTP'03 IFIP Working Group 1.6 on Term Rewriting 4th Int. Workshop on Rule Based Programming, RULE'03 16th Int. Workshop on Unification, UNIF'03 12th Int. Workshop on Functional and (Constraint) Logic Prog., WFLP'03 3rd Int. Workshop on Red. Strat. in Rewriting and Programming, WRS'03 6th Int. Workshop on Termination, WST'03 DATES RDP : June 8 - 14, 2003 RTA'03 : June 9 - 11 TLCA'03: June 10 - 12 FTP'03 : June 12 - 14 WG 1.6 : June 12 RULE'03: June 9 UNIF'03: June 8 - 9 WFLP'03: June 12 - 13 WRS'03 : June 8 WST'03 : June 13 - 14 ORGANIZERS The ELP group at the Universidad Politecnica de Valencia Officials: Salvador Lucas (chair of the organizing committee) Elvira Albert (secretary) Maria Alpuente (workshops chair) Jose Hernandez (local arrangements) Javier Oliver (secretary) Maria Jose Ramirez (local arrangements chair) German Vidal (publicity chair) CONTACT Salvador Lucas Departamento de Sistemas Informaticos y Computacion (DSIC) Universidad Politecnica de Valencia Camino de Vera, s/n E-46022 Valencia (Spain) phone: + 34 96 387 7353 (73531) fax: + 34 96 387 7359 e-mail: slucas(a)dsic.upv.es URL: http://www.dsic.upv.es/users/elp/slucas.html FURTHER INFORMATION RDP website: http://www.dsic.upv.es/~rdp03 The ELP group: http://www.dsic.upv.es/users/elp/elp.html **************************************************************************

1 0

RE: defining (-> Bool) as a set
by Simon Peyton-Jones 23 Apr '02

23 Apr '02

Hal, [I think this sort of question would be better on the haskell-cafe list.] I don't think what you want can be done directly. It's the old thing about not having lambdas at the type level. You want: instance Eq a => Coll (\x. x -> Bool) a where ... and you just can't do that. You *can* abstract the second argument of (->): instance Eq a => Coll ((->) Bool) a where ... but not the first. It's a well known shortcoming in Haskell, that you can partially apply type constructors, but you can't do argument permutation. I know of no good solution. Adding type lambdas in their full glory makes type inference pretty much impossible. What we'd like is a compromise. Maybe someone can invent one. But take care. The ground is littered with corpses. Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 23 April 2002 01:30 | To: Jorge Adriano | Cc: Haskell Mailing List | Subject: Re: defining (-> Bool) as a set | | | Yeah, both options suggested are valid, of course. But I | really don't want to have a constructor and I'm using Edison | where Coll is defined something like: | | class Coll c e where | empty :: c e | insert :: c e -> e -> c e | | etc., which precludes the fun dep solution. | | - Hal | | -- | Hal Daume III | | "Computer science is no more about computers | hdaume(a)isi.edu | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume | | On Tue, 23 Apr 2002, Jorge Adriano wrote: | | > | > > class Collection e ce | ce -> e where | > > empty :: ce | > > insert :: e -> ce -> ce | > > member :: e -> ce -> Bool | > > | > > instance Eq a => Collection a (a -> Bool) where | > > empty = (\x -> False) | > > insert e f = (\x -> if x == e then True else f x) | > > member e f = f e | > | > This is way better than my solution... | > | > I had never used multi-parameter classes before, so I forgot the | > functional | > dependency (right name? the "|ce->e"), and there was | obviously no need for my | > extra constructor. | > | > J.A. | > | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0

semi-private exports
by Hal Daume III 23 Apr '02

23 Apr '02

Hi again, all. In my NLP.Prelude file, I define: > newtype Token = Token [Word8] and I export only the type, not the constructor because I don't users of my package to be able to inspect/modify the list directly. However, in my NLP.IO module, in which I define IO for some of my data types, I need to be able to access it directly. In Java/C#, I would make Token public and the constructor protected (i.e., public for the current package but private for other people). I would really like to be able to do something similar. Any ideas? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

module namespaces with "Prelude"
by Hal Daume III 23 Apr '02

23 Apr '02

I'm developing my package "NLP" for supporting common NLP functions and have a set of functions/datatypes that are common to almost all of my modules and I wanted to separate them off into an "NLP.Prelude" file, but this seems not to work. One of my modules imports Prelude (the Haskell one) directly so I can hide a few definitions, but then it looks at NLP/Prelude.lhs and complains that the name of that module "NLP.Prelude" doesn't match "Prelude". SHould I simply name my module "NLP.NLPPrelude" or something (which is ugly, imo) or what? -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 2

how to call Fortran Procedures in Haskell Program?
by Zhe Fu 23 Apr '02

23 Apr '02

Does anybody know how to call Fortran procedures in Haskell program? I tried Green Card, but seems it only works with C codes. Thanks.

3 2