- Haskell-Cafe - Haskell.org

RE: [Haskell-cafe] Passing types as arguments
by Simon Peyton-Jones 12 Mar '04

12 Mar '04

We pass values as proxies for types extensively in the "Scrap your boilerplate" scheme. The paper is on my home page. The 'typeOf' function is a good example. Part II coming up shortly. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | ajb(a)spamcop.net | Sent: 12 March 2004 03:50 | To: haskell-cafe(a)haskell.org | Subject: [Haskell-cafe] Passing types as arguments | | G'day everyone. | | Some time ago a suggestion came up about passing types as arguments | to functions: | | http://www.haskell.org/pipermail/haskell/2003-June/012184.html | | As a matter of curiosity, the topic has come up again on the wiki: | | http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 | | For this example, we don't just want to pass types, we also want to | pattern match on them. | | I'm curious if anyone else has put any thought to this idea. Is it just | a syntax issue, or are there bad interactions with other parts of the | type system? | | Cheers, | Andrew Bromage | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Passing types as arguments
by ajb＠spamcop.net 12 Mar '04

12 Mar '04

G'day everyone. Some time ago a suggestion came up about passing types as arguments to functions: http://www.haskell.org/pipermail/haskell/2003-June/012184.html As a matter of curiosity, the topic has come up again on the wiki: http://haskell.org/hawiki/StudyGroup/GraphExamplesInHaskell/WhySum3 For this example, we don't just want to pass types, we also want to pattern match on them. I'm curious if anyone else has put any thought to this idea. Is it just a syntax issue, or are there bad interactions with other parts of the type system? Cheers, Andrew Bromage

1 0

Haskell overview
by ATWOOD,JOHN (HP-Corvallis,ex1) 12 Mar '04

12 Mar '04

> A colleague with a mathematics and Lisp background is wanting to learn > more about Haskell. The books he's looked at concentrate more on building > up from the basics and getting the syntax right, etc., whereas really he's > looking more of a top-down view that makes Haskell's features and behavior > clear and relates them to category theory, etc. Would anyone be able to > suggest some good references? > >-- Mark For lispers, I like to point out this sentence of section 6.4 of the Haskell 98 Report: Haskell provides several kinds of numbers; the numeric types and the operations upon them have been heavily influenced by Common Lisp and Scheme. For mathematicians, I'd recommend the first 5 pages of: Calculating Functional Programs, Jeremy Gibbons, 2002 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# calculating Then I'd mention the Acid Rain Theorem, Fusion Theorem, Wadler's _Theorems for Free!_. When I'd show some exemplary fp programs: Bridging the Algorithm Gap: A Linear-Time Functional Program for Paragraph Formatting. Oege de Moor and Jeremy Gibbons, 1999 http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html# para Financial Contracts: An Adventure in Financial Engineering, 2000 Simon Peyton Jones, Jean-Marc Eber, and Julian Seward http://www.lexifi.com/resources.html#paper Functional Specification of JPEG Decompression, and an Implementation for Free, Jeroen Fokker, 1995 http://citeseer.nj.nec.com/72092.html Modeling Web Interactions, Paul Graunke, Robert Bruce Findler, Shriram Krishnamurthi, Matthias Felleisen, 2003 http://citeseer.nj.nec.com/graunke03modeling.html Haskell Server Pages Functional Programming and the Battle for the Middle Tier, Erik Meijer, Dannyy van Velzen, 2000 http://citeseer.nj.nec.com/318262.html Writing High-Performance Server Applications in Haskell, Case Study: A Haskell Web Server, Simon Marlow, 2000 http://www.haskell.org/~simonmar/bib.html (about the 4th one down) And then, the more introductory material: Why Functional Programming Matters, John Hughes http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html and here's a summary of the paper: http://www.cs.auckland.ac.nz/~j-hamer/360/why-fp-matters.html Section 3.1.3 of SICP: http://mitpress.mit.edu/sicp/ Why no one uses functional languages, Philip Wadler, 1998 http://citeseer.nj.nec.com/wadler98why.html here's an old, but still relevant summary of some issues keeping fp from taking over the world: http://www.cs.colorado.edu/~zorn/cs5535/Fall-1997/haskell-summary.html Some general links: http://haskell.readscheme.org/ http://www.haskell.org Hope this isn't too overwhelming, but it was an opportunity for me to gather my thoughts. Enjoy, John Atwood

1 0

Re: Polymorphic lists...
by oleg＠pobox.com 11 Mar '04

11 Mar '04

[Moving to Haskell-cafe from http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006390.ht… http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006393.ht… I hope y'all don't mind the move: the discussion of polymorphic lists is of general interest and is not limited to GHC. Besides, they serve coffee in here, albeit virtually. However, they charge for it virtually, too.] Keean Schupke wrote: > The list indexed by integers cannot determine the type of the > return value through induction on the class... in other words > it cannot determine the return type of the lookup function > until runtime: you can see this in the class instance for 'tke' > > > instance (TH a (a,b), TH W b) => TH W (a,b) where > > tke (W 0) th@(h,t) f = f h th > > tke (W n) (h,t) f = tke (W$ n-1) t f > > On the other hand indexing by natural numbers allows the compiler > to know the return type (and avoid the use of existentials) > because it is determined at compile time... you can see this because > the recursion termination is done by the type signatures in the instance > not the pattern guards of the function. > > instance Relation r => RIndex Zero (a `RCons` r) a where > rIndex Zero (x `RCons` _) = x > instance RIndex Idx r b => RIndex Idx (a `RCons` r) b where > rIndex (Suc n) (_ `RCons` xs) = rIndex n xs I concur wholeheartedly. I have expressed the same sentiment: http://www.haskell.org/pipermail/haskell/2003-August/012493.html http://www.haskell.org/pipermail/haskell/2003-June/011939.html The reason the previous message implemented indexing by true Int is because Ralf Laemmel specifically asked for it (plus it is much harder to do). Keean Schupke wrote: > It looks like most of this stuff has been done before... but I don't think > there is any of it in the ghc libraries. I needed this code for a real > application, and could not find anything suitable so I rolled my own. > > What do people think - is there a case for getting this stuff in the libs, > should we write a functional pearl? does anyone have any comments about > the code I posted, or how it could be improved? It is indeed a very good question. Just for the sake of it, here's a little bit simplified version of your example. Labels are done differently. > {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances #-} > module Foo where > data Z = Z > data S a = S a > > class Nat a where n2n:: a-> Int > instance Nat Z where n2n _ = 0 > instance (Nat a) => Nat (S a) where n2n _ = 1 + n2n (undefined::a) > > -- keyed access > class (Nat n) => MLookup n a r where > mLookup :: r -> n -> a > instance MLookup Z a (a,r) where > mLookup r _ = fst r > instance MLookup n a r => MLookup (S n) a (a,r) where > mLookup (_,xs) _ = mLookup xs (undefined::n) > instance MLookup n a r => MLookup n a (b,r) where > mLookup (_,xs) n = mLookup xs n > > -- Positional access > class (Nat n) => MIndex n a r | n r -> a where > midx:: r -> n -> a > instance MIndex Z a (a,r) where midx (x,_) _ = x > instance (MIndex n a r) => MIndex (S n) a (b,r) where > midx (_,xs) _ = midx xs (undefined::n) The example now reads > newtype Name a = Name a deriving Show > newtype Size a = Size a deriving Show > newtype Weight a = Weight a deriving Show > > infixr 5 &+ > (&+) = (,) > test = (Name "Box") &+ (Size (3::Int)) &+ (Weight (1.1::Float)) > &+ (Name "AnotherBox") &+ (Size (42::Int)) &+ (Weight (24.09::Float)) > &+ () Note that at run-time, (Name "Box") is the same as "Box". Name is a compile-time-only label that incurs no run-time overhead. So, the essence is the same -- a polymorphic associative list where keys are ephemeral (have no run-time representation). "mLookup r n" finds the n-th association in this list of a type a. In the present representation, labels and values are specified together. There is no need for a type declaration for test. The compiler will figure it out. The name and the size of the first box *Foo> mLookup test Z::(Name String) Name "Box" *Foo> mLookup test Z::(Size Int) Size 3 and of the second one *Foo> mLookup test (S Z)::(Name String) Name "AnotherBox" *Foo> mLookup test (S Z)::(Size Int) Size 42 We can also access the element of the array by their absolute position: *Foo> midx test Z Name "Box" *Foo> midx test (S Z) Size 3 *Foo> midx test (S (S (S Z))) Name "AnotherBox" Decimal types for indices (rather than unary, as above) would make for a nicer interface. We can easily write a right fold > class MFoldr a r where > mfoldr :: (a -> b -> b) -> b -> r -> b > instance (MFoldr a r) => MFoldr a (a,r) where > mfoldr f z r = f (fst r) $ mfoldr f z (snd r) > instance MFoldr a () where > mfoldr f z r = z > instance MFoldr a r => MFoldr a (b,r) where > mfoldr f z r = mfoldr f z (snd r) and find out how many names are in our list *Foo> mfoldr (\ (Name (a::String)) n -> n + 1) 0 test 2 and the total sizes of our boxes *Foo> mfoldr (\ (Size s) a -> a + s) (0::Int) test 45 Incidentally, this polymorphic array may be a model of an extensible record with row polymorphism and even polymorphic labels. Yet another record proposal.

1 0

matching constructors
by Vadim Zaliva 09 Mar '04

09 Mar '04

Hi! I am new to Haskell, but I have background in various programming languages (including Lisp) I have very basic question, if there is a way to match algebraic types constructors besides use of pattern matching. I wrote today code like this: data Flag = Verbose | Input String | Output String | Filter String deriving Show instance Eq Flag where Verbose == Verbose = True Input _ == Input _ = True Output _ == Output _ = True Filter _ == Filter _ = True _ == _ = False findFlag :: Flag -> [Flag] -> Flag findFlag f [] = f findFlag y (x:xs) = if x == y then x else findFlag y xs If there is a cleaner way to implement findFlag and Eq Flag? Vadim -- "La perfection est atteinte non quand il ne reste rien a ajouter, mais quand il ne reste rien a enlever." (Antoine de Saint-Exupery)

5 8

HaRe import problem
by Georg Martius 08 Mar '04

08 Mar '04

Hi, I have a problem with Haskell Refactoring. I use the last snapshot from 26/02/2004 and emacs. If I have a source file with an import of a libary module e.g. Text.XML.HaXml.OneOfN I get: Source files missing for (add files with 'pfe add' or 'pfe chase'): Text.XML.HaXml.OneOfN, needed by Test Cheers, Georg

1 0

Haskell BDD library?
by Hans-Wolfgang Loidl 07 Mar '04

07 Mar '04

Hi, We are just starting on a project of parallelising a symbolic model checking algorithm, which operates on BDDs (binary-decision diagrams), in GpH. Does anyone have a Haskell implementation of such a library around and is willing to share it? Also, pointers to possibly useful BDD libraries, either in Haskell or lesser languages, would be welcome. Cheers, -- Hans-Wolfgang Loidl Ludwig-Maximilians-University Munich Tel: +49 89 / 2180 9864 Institut f. Informatik Fax: +49 89 / 2180 9338 Oettingenstr 67 Email: hwloidl(a)informatik.uni-muenchen.de D 80538 Munich URL: http://www.tcs.informatik.uni-muenchen.de/~hwloidl/

2 1

Fun with Haskell, runST, MArray, and a few queens.
by David Sankel 05 Mar '04

05 Mar '04

Hello Enthusiasts, My fiancee was assigned the n-queens problem in her Data Structures class. It was a study in backtracking. For those unfamiliar with the problem: one is given a grid of n x n. Return a grid with n queens on it where no queen can be attacked by another. Anyway, I decided to try an implementation in Haskell (as I often do with her assignments). Instead of the imperative approach (adding a queen and then getting rid of it), I opted for a functional one (the grid is passed to recursive calls, etc.). The interesting thing about this assignment is the runtimes: (n=10) ghc 58.749s ghc -O 12.580s javac 1.088s The Haskell version takes significantly longer (and it gets worse for larger inputs). So it seems that imperative algorithms are much better for certain problems. Since Haskell is supposed to have the ability to run imperative algorithms, I was wondering if any of you could explain how runST and MArray could be used to solve this problem (or is there a better way?). I am also interested in the run times you get with these two implementations of the n-queens problem. David module Main where import Array import Maybe boardSizeToTest = 10 main = print $ fromJust $ solution (emptyBoard boardSizeToTest) boardSizeToTest --The Board datatype. A n x n array indexed starting with 1. data Board = Board Int (Array (Int,Int) Int) deriving Eq instance Show Board where show (Board n b) = concat [ (printLine b a) ++ "\n" | a <- [n,n-1..1] ] where printLine board row = concat [ (str (board ! (row,a))) | a <- [1..n] ] str (-1) = "q" --It's a queen str 0 = "." --It's an empty spot str a = show a --It's a spot that can be attacked by a queen --Helper function from Gentle Introduction to Haskell mkArray :: (Ix a) => (a -> b) -> (a,a) -> Array a b mkArray f bnds = array bnds [(i, f i) | i <- range bnds] --Another helper function to update arrays (/-) :: (Ix a) => Array a b -> [(a, (b -> b))] -> Array a b (/-) array s = array // (map (\ (a, f) -> (a,f (array!a))) s) --An empty chessboard emptyBoard :: Int -> Board emptyBoard n = Board n $ mkArray (\_->0) ((1,1),(n,n)) --Adds a queen to the board and adds 1 in all the positions the queen --could feasible move. addQueen :: Board -> (Int,Int) -> Board addQueen b@(Board n board) c = Board n $ newBoard // [(c, -1)] where Board _ newBoard = queenHelper b (+1) c --Removes a queen from the board and subtracts 1 in all the positions the queen --could have feasible moved. removeQueen :: Board -> (Int,Int) -> Board removeQueen b@(Board n board) c = Board n $ newBoard // [(c, 0)] where Board _ newBoard = queenHelper b ((-)1) c queenHelper :: Board -> (Int->Int) -> (Int, Int) -> Board queenHelper (Board n board) f (row,column) = Board n $ board /- horizontal /- vertical /- negPosDiag /- posNegDiag /- negNegDiag /- posPosDiag where vertical = [ ((r,column),f) | r <- [1..n] ] horizontal = [ ((row,c),f) | c <- [1..n] ] negPosDiag = [ ((row-i,column+i),f)| i <- [1..(min (n-column) (row-1))]] posNegDiag = [ ((row+i,column-i),f)| i <- [1..(min (column-1) (n-row))]] negNegDiag = [ ((row-i,column-i),f)| i <- [1..(min (column-1) (row-1))]] posPosDiag = [ ((row+i,column+i),f)| i <- [1..(min (n-column) (n-row))]] --Returns all the positions on the board that do not have a queen and cannot --be attacked by a queen already on the board. possiblePositions (Board n board) = filter (\a -> board ! a == 0) [ (row,column) | row <- [1..n], column <- [1..n] ] --Finds a solution given a board and a number of queens to put on it solution :: Board -> Int -> Maybe Board solution board 0 = Just board solution board i = let solutions = catMaybes $ [ solution (addQueen board c) (i-1) | c <- (possiblePositions board) ] in if solutions == [] then Nothing else Just $ head solutions

5 5

[Haskell-cafe] Re: Fun with Haskell, runST, MArray, and a few queens. (Imperative Haskell Version)
by David Sankel 05 Mar '04

05 Mar '04

> I say this is a case of bad code. Of course language <foo> is faster and > better if you write horribly bad code in language <bar>. > Taking the first solution found by searching with google I get times > around 0.015s (real) for the Haskell version and 1.7s for your Java > solution (which also seems to be overcomplicated to me). That's cool. Although the java algorithm is beyond any doubt overcomplicated, I'd like to reproduce it using Haskell's imperative constructs because not all backtracking algorithms have a simple closed form solution. What I've done using monads is a little better in speed, but not the huge improvement I was expecting. Any comments as to what I'm doing wrong here? Updated Table: ghc�� 58.749s ghc -O�� 12.580s ghc -O (monad version) 8.284s javac�� 1.088s David module Main where import Control.Monad.ST import GHC.Arr import Maybe import Ix main = print $ runST something n = 10 -- Used only for output data Board = Board Int (Array (Int,Int) Int) deriving Eq instance Show Board where show (Board n b) = concat [ (printLine b a) ++ "\n" | a <- [n,n-1..1] ] where printLine board row = concat [ (str (board ! (row,a))) | a <- [1..n] ] str (-1) = "q" --It's a queen str 0 = "." --It's an empty spot str a = show a --It's a spot that can be attacked by a queen --Finds a solution given a board and a number of queens to put on it solution board 0 = return True solution board i = do possibleP <- (possiblePositions board) trySolution possibleP where trySolution [] = return False trySolution (c:cs) = do addQueen board c good <- solution board (i-1) if good then return True else do removeQueen board c trySolution cs --Returns all the positions on the board that do not have a queen and cannot --be attacked by a queen already on the board. -- possiblePositions board = -- do -- p <- sequence [ readSTArray board (row,column) >>= -- (\a -> return (a == 0,(row,column))) -- | row <- [1..n], column <- [1..n] ] -- return $ map (\(_,b)->b) $ filter (\(a,_)-> a) p possiblePositions board = do -- let indices = range $! boundsSTArray board let indices = [ (row,column) | row <- [1..n], column <- [1..n] ] p <- sequence $ map (\i -> readSTArray board i >>= (\a -> if a == 0 then return $ Just i else return Nothing )) indices -- return $ map (\(_,b)->b) $ filter fst p return $ catMaybes p arrayToBoard board = do it <- sequence [ readSTArray board (a,b) >>= (\s -> return ((a,b),s)) | a <- [1..n], b <- [1..n] ] return (Board n (array ((1,1),(n,n)) it)) emptyBoard = newSTArray ((1,1),(n,n)) 0 something = do board <- emptyBoard solution board n arrayToBoard board --Adds a queen to the board and adds 1 in all the positions the queen --could feasible move. addQueen b c = do queenHelper b (+1) c writeSTArray b c (-1) --Removes a queen from the board and subtracts 1 in all the positions the queen --could have feasibly moved. removeQueen b c = do queenHelper b (\a -> a - 1) c writeSTArray b c 0 --Helper function to update arrays (/-) array s = do sequence_ [ readSTArray array b >>= \n -> writeSTArray array b $! (c n) | (b,c) <- s ] return array queenHelper board f (row,column) = do board /- (horizontal ++ vertical ++ negPosDiag ++ posNegDiag ++ negNegDiag ++ posPosDiag) where vertical = [ ((r,column),f) | r <- [1..n] ] horizontal = [ ((row,c),f) | c <- [1..n] ] negPosDiag = [ ((row-i,column+i),f)| i <- [1..(min (n-column) (row-1))]] posNegDiag = [ ((row+i,column-i),f)| i <- [1..(min (column-1) (n-row))]] negNegDiag = [ ((row-i,column-i),f)| i <- [1..(min (column-1) (row-1))]] posPosDiag = [ ((row+i,column+i),f)| i <- [1..(min (n-column) (n-row))]]

1 0

Instance Problem
by 98222＠oa.cmbchina.com 05 Mar '04

05 Mar '04

How can I do this: class M a where tok::a->String instance M String where tok s="String" instance Num a=>M a where tok n="Number" instance (for all other types a)=>M a where tok x="Other"

1 0