- Haskell-Cafe - Haskell.org

Type hacking help
by Chris Smith 19 Jul '07

19 Jul '07

I've just written my first real piece of type system hacking in Haskell. I think it turned out okay, but if any of you more experienced folk have suggestions, I'd appreciate them. Code follows. More explanation is at http://cdsmith.wordpress.com/2007/07/19/parsing-cfgs-and-type-hacking/ {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE NoMonomorphismRestriction #-} data Var a = Var String data RHS a b = RHS a b (&) = RHS -- a convenient operator infixr 5 & {- (Action a b c) means the following: A production with a right hand side of type: a may be associated with a semantic rule of type: b to produce a rule with semantic result type: c -} class Action a b c | a b -> c, a c -> b instance Action (Var x) (x -> y) y instance Action Char y y instance Action () y y instance (Action a b c) => Action (RHS (Var x) a) (x -> b) c instance (Action a b c) => Action (RHS Char a) b c {- The RuleSet monad is used to define rules of a grammar in a convenient 'do' notation. -} data Rule = forall a b c. (Action a b c) => Rule (Var c, a, b) data RuleSet x = RuleSet ([Rule], x) instance Monad RuleSet where a >>= k = let RuleSet (r1, v1) = a RuleSet (r2, v2) = k v1 in RuleSet (r1 ++ r2, v2) return x = RuleSet ([], x) (==>) :: (Action a b c) => Var c -> a -> b -> RuleSet () (==>) lhs rhs sem = RuleSet ([Rule (lhs, rhs, sem)], ()) infixr 4 ==> {- Grammar. A grammar is a set of rules together with a start symbol. -} data Grammar a = Grammar (Var a) [Rule] grammar s (RuleSet (rs, x)) = Grammar s rs {- Sample grammar. The parentheses in the let bindings are required: they force the rules to be monomorphic, which is needed for type checking to work properly. -} g = let ( expr ) = Var "expression" ( term ) = Var "term" ( termmore ) = Var "term operator" ( fact ) = Var "factor" ( factmore ) = Var "factor operator" ( digit ) = Var "digit" ( digits ) = Var "digits" in grammar expr $ do expr ==> term & termmore $ \x y -> y x termmore ==> () $ \x -> x termmore ==> '+' & term & termmore $ \x y z -> y (x + z) termmore ==> '-' & term & termmore $ \x y z -> y (x - z) term ==> fact & factmore $ \x y -> y x factmore ==> () $ \x -> x factmore ==> '*' & fact & factmore $ \x y z -> y (x * z) factmore ==> '/' & fact & factmore $ \x y z -> y (x / z) fact ==> '(' & expr & ')' $ \x -> x fact ==> digit & digits $ \x y -> y x digits ==> () $ \x -> x digits ==> digit & digits $ \x y z -> y (10*x + z) digit ==> '0' $ 0 digit ==> '1' $ 1 digit ==> '2' $ 2 digit ==> '3' $ 3 digit ==> '4' $ 4 digit ==> '5' $ 5 digit ==> '6' $ 6 digit ==> '7' $ 7 digit ==> '8' $ 8 digit ==> '9' $ 9 Thanks, -- Chris Smith

1 0

Master's thesis project at Philips Research
by Robert van Herk 19 Jul '07

19 Jul '07

At Philips Research (Eindhoven, The Netherlands), we have a Haskell master-thesis project in the context of interactive toys. We are developing a platform for serious toys and games. In this project, we add advanced interactivity based on wireless sensors to traditional toy designs. This can be used to create a whole range of new, revolutionary, exciting toys and games. One of the design goals is that it will be easy for a non-technical person to write applications for the toys and games. For this we are developing a programming language. In this context, we are looking for a student. The project would encompass be the following: - Design and finetune a grammer for this language - Create a parser and compiler for this language - Implement an interpreter to run the compiled code on embedded hardware Some design goals are: - The language should cover the functionality needed to elegantly program the required set of applications - The language should be easily understandable for a non-technical person We are looking for somebody who: - is a master student in Computer Science - has knowledge of language design and compiler design - can write code that runs well on constrained hardware - is a good “team-player” - can express himself well in English Of course, affinity with story designing or toy designing is advantageous. Please contact me by e-mail if you are interested! Regards, Robert --------------------- Robert van Herk Research Scientist, IT Group, Philips Research High Tech Capus 37 (WY) 7.40 Eindhoven The Netherlands

2 1

Is this haskelly enough? -- errm but every answer is wrong(?)
by Anthony Clayden 19 Jul '07

19 Jul '07

(Or at least the problem is under-specified.) 1. There may be several sub-sequences having the maximum sum. So the type for the solution should be :: Num a => [a] -> [[a]] (Note that the problem didn't ask for the maximum itself.) 2. The inits . tails approach adds a fault: It introduces a sprinkling of empty sub-sequences. These have sum zero. So in case the input list is all negative numbers ... Being a software tester for my day job, I looked first not for an elegant and/or efficient solution; but for where to stretch the boundaries of the problem. > However, the key point is that this is a TRICK QUESTION. <snip>

5 4

Time consumption nub
by Arie Groeneveld 19 Jul '07

19 Jul '07

Hi, Wondering about time space consuming: 'nub' vs 'map head.group.sort' Consider: ry = [1..10000] ++ replicate 13 5 ++ replicate 21 34 *Main> length . nub $ ry 10000 (5.18 secs, 1050000 bytes) *Main> length . map head . group . sort $ ry 10000 (0.03 secs, 6293384 bytes) Time space nub --- + fnub +++ - + is better ;-) Thanks @@i=arie

3 4

Stream processors as arrows
by Miguel Mitrofanov 19 Jul '07

19 Jul '07

I'm trying to do Exercise 2.5.2 from John Hughes's "Programming with Arrows". It asks to make the type SP defined as (notation is slightly different) > data SP a b = Inp (a -> SP a b) | Out b (SP a b) an instance of Arrow, ArrowChoice and ArrowLoop. Some parts of it are straightforward, e.g. > arr f = fix $ \sp -> Inp $ \x -> Out (f x) sp Some are a bit tricky; for "first" I ended up with code > first = fix first' > where first' f sp = Inp $ \(x,z) -> let g = firstL x > h = firstR z > in case sp of Inp _ -> (g . h) f sp > Out _ _ -> (h . g) f sp > firstL x f (Inp fsp) = f $ fsp x > firstL x f sp = first' (firstL x f) sp > firstR z f (Out y sp) = Out (y,z) $ f sp > firstR z f sp = first' (firstR z f) sp which is a bit funny. But the real problem I don't know how to deal with is "loop". My first attempt was somethig like this: > loop (Out (y,z) sp) = Out y $ loop' z loop sp > where loop' z f (Inp fsp) = Inp $ \x -> f $ fsp (x,z) > loop' z f (Out (y,z') sp) = Out y $ loop' z' (loop' z f) sp since I thought it's pointless to make a loop that don't do any output. But then I ran into trouble: *StreamProc> process (loop returnA) [1..10] *** Exception: g:/StreamProc.hs:(26,4)-(28,90): Non-exhaustive patterns in function loop So I realized that both arr and first are doing input first and output second, and that causes this error. I've tried to fix this with > loop (Inp fsp) = Inp $ \x -> let Out (y,z) sp = fsp (x,z) in Out y $ loop sp This works as desired: *StreamProc> process (loop returnA) [1..10] [1,2,3,4,5,6,7,8,9,10] But it seems to solve the problem by shifting it one step away from us. I'm not sure this is enough. Any advice/suggestions?

2 2

xkcd #287 "NP-Complete"
by Tom Pledger 19 Jul '07

19 Jul '07

We've seen some nice concise solutions that can deal with the original problem: solve 1505 [215, 275, 335, 355, 420, 580] I'll be a nuisance and bring up this case: solve 150005 [2, 4, 150001] A more scalable solution is to use an explicit heap that brings together all the ways to get to each partial sum. I coded one using Data.Map, but it's a bit long-winded and ugly. Perhaps a purpose-built heap monad would make it more elegant... as long as it could be reused elsewhere. Just musing. :-) - Tom

5 7

historical question about Haskell and Haskell Curry
by Michael Vanier 19 Jul '07

19 Jul '07

We always say that Haskell is named for Haskell Curry because his work provided the logical/computational foundations for the language. How exactly is this the case? Specifically, does anyone claim that Curry's combinatorial logic is more relevant to the theoretical foundations of Haskell than e.g. Church's lambda calculus? If not, why isn't Haskell called "Alonzo"? ;-) Mike

5 5

Clearly, Haskell is ill-founded
by Thomas Conway 19 Jul '07

19 Jul '07

I don't know if you saw the following linked off /. http://www.itwire.com.au/content/view/13339/53/ An amazon link for the book is here: http://www.amazon.com/Computer-Science-Reconsidered-Invocation-Expression/d… The basic claim appears to be that discrete mathematics is a bad foundation for computer science. I suspect the subscribers to this list would beg to disagree. Enjoy, T. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

19 32

Is this haskelly enough?
by James Hunt 19 Jul '07

19 Jul '07

Hi, As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http://www.rubyquiz.com/quiz131.html) in Haskell. Would someone be kind enough to cast their eye over my code? I get the feeling there's a better way of doing it! subarrays :: [a] -> [[a]] subarrays [] = [[]] subarrays xs = (sa xs) ++ subarrays (tail xs) where sa xs = [ys | n <- [1..length xs], ys <- [(take n xs)]] maxsubarrays :: [Integer] -> [Integer] maxsubarrays xs = msa [] (subarrays xs) where msa m [] = m msa m (x:xs) | sum x > sum m = msa x xs | otherwise = msa m xs --for testing: should return [2, 5, -1, 3] main = maxsubarrays [-1, 2, 5, -1, 3, -2, 1] I've read tutorials about the syntax of Haskell, but I can't seem to find any that teach you how to really "think" in a Haskell way. Is there anything (books, online tutorials, exercises) that anyone could recommend? Thanks, James

21 33

Using Haskell to investigate ML's value restriction
by Brian Hulley 18 Jul '07

18 Jul '07

Hi, Ii is interesting that in ML, the presence of mutable ref cells and parametric polymorphism requires the whole language to be dominated by a "value restriction" [1] to ensure that the type system remains sound, whereas in Haskell, because IORef's can only be created (and used) in the IO monad, no such restriction is necessary. I've often wondered why such a simple thing as using a monad has this magical effect, especially since it seems to me that the real problem lies in the fact that type variables in HMD type inference are not generalised properly due to the absence of an explicit representation of the quantifier, so I decided to try using Haskell's more modern type system to investigate further, using the IO monad together with (unsafePerformIO) and (evaluate) to simulate the execution of an ML program: {-# OPTIONS_GHC -fglasgow-exts #-} module Test where import Data.IORef import System.IO.Unsafe (unsafePerformIO) import Control.Exception (evaluate) ref v = unsafePerformIO $ newIORef v put r f = unsafePerformIO $ writeIORef r f get r = unsafePerformIO $ readIORef r -- Gives a core dump as expected test1 :: IO () test1 = do let r = ref (\x -> x) evaluate (put r (\x -> x + 1)) evaluate (get r True) return () (test1) is based on one of the ML examples in [1], and when executed, causes a segmentation fault. The reason seems to be the strange type that is assigned to (r): *Test> let r = ref (\x -> x) *Test> :t r r :: forall t. IORef (t -> t) *Test> (To run this you need to use ghci -fglasgow-exts Test.hs to get ghci 6.6.1 to display the quantifier.) What's strange (to me) about the above typing is that the "forall" has moved outside the IORef constructor. In other words, although we supplied the constructor with a function which can operate on any value, we got back something which, for any value, contains a function which can operate on it. The reason afaics that (test1) goes wrong is that the let binding causes (r) to be bound to the type above, so the argument matches both forall a. Num a => a -> a and Bool -> Bool so the action (evaluate (get r True)) tries to apply a function which expects a number to a Bool. However if we add an explicit type to (r) to get (what I see as) the expected quantification, the type checker correctly rejects the program: test2 :: IO () test2 = do let r :: IORef (forall a. a -> a) = ref (\x -> x) evaluate (put r (\x -> x + 1)) evaluate (get r True) return () "no instance for Num a ..." which might seem like a reason not quite related to our chain of thought so I also tested this using: test3 :: IO () test3 = do let r :: IORef (forall a. a -> a) = ref (\x -> x) evaluate (put r (\'c' -> 'c')) evaluate (get r True) return () which gives "couldn't match expected type `a' (a rigid variable) against inferred type `Char'". In other words, the IORef must always contain a function that works with anything - we can't just give it a more specialized function, so the program is rejected for the reasons we expect. Interestingly, even without type annotations, if we use a case instead of a let, the typechecker also rejects the program: test4 :: IO () test4 = case ref (\x -> x) of r -> do evaluate (put r (\'c' -> 'c')) evaluate (get r True) return () this time by noting that (Bool -> t) does not match (Char -> Char). This illustrates (afaiu) that "case" does not introduce any quantification, in contrast to "let" hence the uninstantiated meta-tyvars of r have to unify with both its uses. In conclusion, it seems that the "magic" given by always having to use IORef's inside the IO monad (without unsafePerformIO of course) is due to the fact that when used this way types involving IORefs never get generalized wrongly since they're never created by a "let" binding. Another conclusion is that if we wanted at some point to have another new strict language with Haskell's nice type system and syntax as an alternative to the ML family, and we also wanted to have references (and continuations), then either the rule for generalizing the meta-type variables in a "let" binding would have to be changed or else we would still have to use monads. I'd be interested to know if the use of impredicative types would automatically solve the "wierd quantification" problem, since: *Test> :t ref ref :: forall a. a -> IORef a therefore applying this to an argument of type (forall b. b -> b) should hopefully give a result of type (IORef (forall b. b -> b)), thus the use of impredicative types might allow such a strict variant of Haskell to use side-effects instead of monads while still retaining type soundness... ? Best regards, Brian. [1] http://www.smlnj.org/doc/Conversion/types.html

1 0