- Haskell-Cafe - Haskell.org

How to construct a lazy list of eagerly-evaluated items?
by Vladimir Ch. 23 May '10

23 May '10

I'm using Project Euler to learn Haskell. In particular, I'm writing a program for Problem 18: http://projecteuler.net/index.php?section=problems&id=18. As a solution, I'm constructing a list, containing maximum sums of values on a path from top of the triangle to a given item. In this list, item value equals value of an item from an input list plus maximum of values of the "top neighbours", taken from the same list we're constructing. Here's the program: BEGIN CODE triangle18 = [75...etc - definition of the input triangle sqrti n = truncate (sqrt (fromIntegral n)) -- returns true if a number is an exact square isSquare n = n == r * r where r = sqrti n -- returns true if a number is a triangular numberx isTriangular n = isSquare (8 * n + 1) -- returns index of the top-right neighbour prevRight i = i - (sqrti (8 * i + 1) - 1) `div` 2 -- returns index of the top-left neighbour prevLeft i = prevRight i - 1 -- returns the list of top neighbours (at most 2) prev i | i == 0 = [] | isTriangular i = [prevRight i] | isTriangular (i + 1) = [prevLeft i] | otherwise = [prevLeft i, prevRight i] -- returns the list of 'path sums' for a given list of input numbers maxPaths vals@(v:vs) = v : zipWith mpath [1..] vs where mpath i val = val + maximum [(maxPaths vals) !! pi| pi <- prev i] result18 = maximum (maxPaths triangle18) END CODE The program works, but consumes obscene amount of memory. I suspect that it's because of lazy evaluation of items in the list we're constructing (and also using during construction). How can I force eager evaluation of items, put into the list? Any other comments and suggestions are also very welcome. I know index-based item lookup in a list is not efficient, but I'll take care of this later (I don't know much about arrays yet). For now, I'm more concerned with the memory usage.

2 2

making the GHC Api not write to stderr
by Phyx 22 May '10

22 May '10

I was wondering how to forcibly quiet down the API. I have a custom handler in place, but when I call the function on failure both my handler gets called and somewhere somehow errors get printed to the stderr, which I really need to avoid. My current code looks like getModInfo :: Bool -> String -> String -> IO (ApiResults ModuleInfo) getModInfo qual file path = handleSourceError processErrors $ runGhc (Just libdir) $ do dflags <- getSessionDynFlags setSessionDynFlags $ configureDynFlags dflags target <- guessTarget file Nothing addTarget target setSessionDynFlags $ dflags { importPaths = [path] } load LoadAllTargets graph <- depanal [] False let modifier = moduleName . ms_mod modName = modifier $ head graph includes = includePaths dflags imports = importPaths dflags dflags' <- Debug.trace (moduleNameString modName) getSessionDynFlags setSessionDynFlags $ dflags' { includePaths = path:includes , importPaths = path:imports } parsed <- parse modName checked <- typecheckModule parsed

4 7

ANN: has-0.4 Entity based records
by HASHIMOTO, Yusaku 22 May '10

22 May '10

Hello, I'm pleased to announce the release of my new library, named "has", written to aim to ease pain at inconvinience of Haskell's build-in records. With the has, You can reuse accessors over records to write generic function, combine records with another. Repository is at GitHub: http://github.com/nonowarn/has Uploaded on Hackage: http://hackage.haskell.org/package/has So you can install this by "cabal install has" You can use the has in three steps (without counting installation). 1. Write {-# OPTIONS_GHC -fglasgow-exts #-} top of your code, import Data.Has module. > {-# OPTIONS_GHC -fglasgow-exts #-} > import Data.Has 2. Define entities. "Entity" is data to index field in records. You can define an entity in one line. > data Foo = Foo; type instance TypeOf Foo = Int (I lied) Before semicolon, declares entity. After semicolon, specifies the type to which the entity points. Define some entities for later examples. > data Bar = Bar; type instance TypeOf Bar = Double > data Baz = Baz; type instance TypeOf Baz = String > data Quux = Quux; type instance TypeOf Quux = Bool 3. Define Records by concatinating fields of entities. > type MyRecord = FieldOf Foo :&: FieldOf Bar :&: FieldOf Baz This is almost same as writing < data MyRecord = MyRecord { foo :: Int < , bar :: Double < , baz :: String < } To construct a value of record, remove colons and replace entities in record with values, and uncapitalize some words. > aRecord :: MyRecord > aRecord = fieldOf 42 & fieldOf 3.14 & fieldOf "string" And you can play with it. To read/write/modify a value of field in records, you can use functions with names stealed from data-accessor. But uses value-level entities instead of accessors. < Foo ^. aRecord -- Reading < Foo ^= 4649 $ aRecord -- Writing < Foo ^: (*2) $ aRecord -- Modifying If we have another record type contains Foo field, You can still access the field in the same way. > type AnotherRecord = FieldOf Bar :&: FieldOf Foo > anotherRecord :: AnotherRecord > anotherRecord = fieldOf 2.71 & fieldOf 31 < Foo ^. anotherRecord -- And this also works Using these functions and Has constraint, You can write generic functions over records. > fooIsGreaterThan :: (Has Foo r) => r -> Int -> Bool > fooIsGreaterThan r x = (Foo ^. r) > x < aRecord `fooIsGreaterThan` 40 -- evaluated to True < anotherRecord `fooIsGreaterThan` 40 -- evaluated To False Even if you defined another record by combining records by (:&:), you can still access the field, and apply to generic functions. > type MoreRecord = FieldOf Baz :&: FieldOf Quux > type CombinedRecord = AnotherRecord :&: MoreRecord > combinedRecord :: CombinedRecord > combinedRecord = (fieldOf 1.618 & fieldOf 39) & (fieldOf "sowaka" & fieldOf True) > -- We can omit parentheses > -- (even place parens anyware in record) < combinedRecord `fooIsGreaterThan` 40 -- This yet works The Has constraint provides not only genericity but also safety. If the record doesn't satisfy the constraint, the type checker rejects it. > predicateOnRecords :: (Has Foo r, Has Quux r) => r -> Bool > predicateOnRecords r = fooIsGreaterThan r 30 && (Quux ^. r) < predicateOnRecords combinedRecord -- This is OK < predicateOnRecords aRecord -- This yields compile error More examples included in package[1] [1]: http://github.com/nonowarn/has/tree/master/examples/ This library is inspired by HList[2], and interfaces are stealed from data-accessors[3]. And lenses[4], fclabels[5], and records[6] devote themselves to similar purposes. [2]: http://hackage.haskell.org/package/HList [3]: http://hackage.haskell.org/package/data-accessor [4]: http://hackage.haskell.org/package/lenses [5]: http://hackage.haskell.org/package/fclabels [6]: http://hackage.haskell.org/package/records Enjoy! -nwn

3 9

Performance Issue
by Richard Warburton 22 May '10

22 May '10

A colleague of mine pointed out that ghc wasn't performing as he expected when optimising some code. I wonder if anyone could offer any insight as to why its not noting this common subexpression: main = print $ newton 4 24 newton a 0 = a newton a n = ((newton a (n-1))^2 + a)/(2*(newton a (n-1))) Compiled with 'ghc -O3 --make perf.hs', results in: real 0m5.544s user 0m5.492s sys 0m0.008s However if we factor out the repeated call to the newton method: main = print $ newton2 4 24 newton2 a 0 = a newton2 a n = (x^2 + a)/(2*x) where x = newton2 a (n-1) real 0m0.004s user 0m0.004s sys 0m0.004s It looks to me like Referential transparency should make this a sound optimisation to apply, but ghc isn't doing it even on -O3. regards, Richard

9 13

Re: [Haskell-cafe] Enum instantiation
by Antoine Latter 22 May '10

22 May '10

On Fri, May 21, 2010 at 8:59 PM, R J <rj248842(a)hotmail.com> wrote: > If I type "toEnum 5," the error I get is: > <interactive>:1:0: > Ambiguous type variable `a' in the constraint: > `Enum a' arising from a use of `toEnum' at <interactive>:1:0-7 > Probable fix: add a type signature that fixes these type variable(s) > *Main> Here the problem is not in your instance of Enum, but that GHCi doesn't know which instance of enum to use. In most code this isn't a problem, because the surrounding context often gives enough information for the type-checker to work with. But when there isn't enough context, you'll need to provide a type signature. Does "toEnum 5 :: Day" work? Antoine

1 0

Enum instantiation
by R J 22 May '10

22 May '10

I'd like to make "Day" an instance of class "Enum," but the definition of toEnum below seems to be completely wrong, because integers seem not permit pattern matching. How is toEnum defined? Thanks. data Day = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday deriving (Eq, Ord, Show) instance Enum Day where fromEnum Sunday = 0 fromEnum Monday = 1 fromEnum Tuesday = 2 fromEnum Wednesday = 3 fromEnum Thursday = 4 fromEnum Friday = 5 fromEnum Saturday = 6 toEnum 0 = Sunday toEnum 1 = Monday toEnum 2 = Tuesday toEnum 3 = Wednesday toEnum 4 = Thursday toEnum 5 = Friday toEnum 6 = Saturday _________________________________________________________________ Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

3 2

ambiguous type variable problem when using forall, multiparameter type classes, and constraints on polymorphic values (and syb-with-class)
by Jeremy Shaw 21 May '10

21 May '10

Hello, I am trying to understand why I am getting an ambigious type variable error, and what I can do to work around it. The problem is occurring while trying to use syb-with-class, but I have stripped it down to it's bare essentials, so the following code is self-contained, and does not require an understanding of syb-with-class. > {-# LANGUAGE RankNTypes, KindSignatures, MultiParamTypeClasses, FlexibleInstances, ScopedTypeVariables, FlexibleContexts #-} > module Main where A Proxy data type used to pass some extra type info around in gmapQ. > data Proxy (a :: * -> *) = Proxy A simple multiple parameter type class. > class Data (ctx :: * -> *) a gmapQ takes a function, forall a. (Data ctx a) => a -> r, applies the function to all the immediate sub-types of 'a' and collects the results as a list. This is possible because the 'a' is forall'd, and (in the real implementation) the Data class provides the mechanisms for accessing all the immediate sub-types of 'a' and doing useful things with them. > gmapQ :: Proxy ctx -> (forall a. (Data ctx a) => a -> r) -> (forall a. (Data ctx a) => a -> [r]) > gmapQ = undefined Now we create a context. > data Foo m a = Foo { unFoo :: m a } And create a Data instance for it. > instance Data (Foo m) a Here is an example that attempts to recursively apply itself to all the subtrees. (I believe this function will ultimately return 0, since it tries to sum the results of the children. When you reach types with no more sub-types, I think you will get an empty list, and sum [] == 0. Though it's not really important to the issue at hand). > bar1 :: forall a m r. (Data (Foo m) a, Num r) => a -> r > bar1 x = sum $ gmapQ (undefined :: Proxy (Foo m)) bar1 x The problem I have is when I try to add an additional constraint on 'm', such as (Monad m) => > -- bar2 :: forall a m r. (Monad m, Data (Foo m) a, Num r) => a -> r > -- bar2 x = sum $ gmapQ (undefined :: Proxy (Foo m)) (bar2 :: forall b. (Monad m, Data (Foo m) b, Num r) => b -> r) x I get the error: /tmp/a.lhs:48:54: Ambiguous type variable `m' in the constraint: `Monad m' arising from a use of `bar2' at /tmp/a.lhs:48:54-57 Probable fix: add a type signature that fixes these type variable(s) Failed, modules loaded: none. Adding all the scoped type variable stuff does not seem to help. Alas, I can not figure out if this is a limitation of the type-checker, or something that is fundamentally impossible. Nor can I figure out how to work around the issue. In my real code I need to define the data instance like: > -- instance (Monad m) => Data (Foo m) a Which, by itself is fine. But that results in my needing to add (Monad m) to the 'bar' function. And that is what I can't figure out how to do.. Thanks! - jeremy

2 1

FW: Why does this Ord-class instance crash?
by R J 21 May '10

21 May '10

Why does the following, trivial code snippet below hang GHCi when I type"Scalene > Failure", and what's the fix? data Triangle = Failure | Equilateral | Isosceles | Scalene deriving (Eq, Show) instance Ord Triangle where Failure < Failure = False Failure < _ = True Equilateral < Failure = False Equilateral < Equilateral = False Equilateral < _ = True Isosceles < Scalene = True Isosceles < _ = False Scalene < _ = False (I tried submitting this to beginners(a)haskell.org, but even though I've signed up for that mailing list, I got a bounce-back saying that I needed admin approval to submit anything to that list, and I haven't heard from an admin, so I'm posting it here.) _________________________________________________________________ The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multiaccount&ocid=PID28…

4 3

Tools to make tidy HTML
by Dmitri O.Kondratiev 21 May '10

21 May '10

Hello! Please advise haskell libraries similar to convert real-world HTML to well-formed XML. I need something similat to "HTML Tidy" library: http://tidy.sourceforge.net/ Thanks! Dmitri

1 0

Register now for: Haskell in Leipzig (Germany), June 4.
by Johannes Waldmann 21 May '10

21 May '10

Schedule and registration for the "Haskell in Leipzig" meeting on June 4 are now on-line: http://www.iba-cg.de/hal5.html It's our fifth meeting, and here are five good reasons to go: * learn Haskell: attend tutorials for beginners * get first-hand information: authors of Leksah, HXT, Hawk give tutorials/talks * share your expert knowledge: at lambda camp * see beyond Haskell: learn dependently typed programming in Agda * relax at BBQ party and listen to strange sounds: unsafePerformance The meeting is presented by http://www.fit-leipzig.de/ , in co-operation with http://www.imn.htwk-leipzig.de/ , http://www.leipziger-medienstiftung.de/, http://www.iba-cg.de/ Best regards, Johannes Waldmann (for the Hal5 program committee)

1 0