- Haskell-Cafe - Haskell.org

Type families vs. functional dependencies -- how to express something
by Tomáš Janoušek 25 May '10

25 May '10

Hello all, for the past few hours I've been struggling to express a certain idea using type families and I really can't get it to typecheck. It all works fine using functional dependencies, but it could be more readable with TFs. From those papers about TFs I got this feeling that they should be as expressive as FDs, and we should use them (some people even occasionally mentioning that FDs may be deprecated in favor of them). Can someone help me make the following work, please? The working code with functional dependencies: > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE FunctionalDependencies #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE UndecidableInstances #-} > {-# LANGUAGE ScopedTypeVariables #-} > > __ = undefined > > data HNil = HNil > data HCons a b = HCons a b > > data A a = A a > data B a = B a > > class X a l p | a -> l p where > ll :: a -> l > pp :: a -> p > > instance X (B l) HNil (B l) where > ll _ = HNil > pp p = p > > instance (X x l p) => X (A t -> x) (HCons t l) p where > ll _ = HCons __ (ll (__ :: x)) > pp p = pp (p (A (__ :: t))) > > -- (inferred) > -- testX :: (X a l (B l)) => a -> B l > testX x = pp x `asTypeOf` B (ll x) The motivation here is that A a represents a variable of type a, B b represents a computation with state b, and functions of type A a -> B b represent a computations with state b that use the first parameter as an accessor for a variable (or, more precisely, state component) of type a. Now, I want testX to take such function (with n parameters) and provide it with those accessors, fixing the type b to contain components of the corresponding accessors only. (The example uses dummy types and undefineds for simplicity.) This pretty much works: testX (B __) :: B HNil testX (\(A _) -> B __) :: B (HCons t HNil) testX (\(A True) -> B __) :: B (HCons Bool HNil) testX (\(A _) (A _) -> B __) :: B (HCons t (HCons t1 HNil)) testX (\(A _) (A _) (A _) -> B __) :: B (HCons t (HCons t1 (HCons t2 HNil))) testX (\(A _) -> B HNil) :: error This is my attempt to rephrase it using type families: > class X' a where > type L a > type P a > ll' :: a -> L a > pp' :: a -> P a > > instance X' (B l) where > type L (B l) = HNil > type P (B l) = B l > ll' _ = HNil > pp' p = p > > instance (X' x) => X' (A t -> x) where > type L (A t -> x) = HCons t (L x) > type P (A t -> x) = P x > ll' _ = HCons __ (ll' (__ :: x)) > pp' p = pp' (p (A (__ :: t))) > > -- (inferred) > -- testX' :: (B (L a) ~ P a, X' a) => a -> P a > testX' x = pp' x `asTypeOf` B (ll' x) Only the X' (B l) instance works, the other produces a strange error: testX' (B __) :: P (B HNil) :: B HNil testX' (\(A _) -> B __) :: error Couldn't match expected type `a' against inferred type `Main.R:L(->) t (B a)' Expected type: P (A t -> B a) Inferred type: B (L (A t -> B a)) Unifying those two types by hand, I get: P (A t -> B a) ~> P (B a) ~> B a B (L (A t -> B a)) ~> B (HCons t (L (B a))) ~> B (HCons t HNil) Hence, a = HCons t HNil. But GHC doesn't get that. I'm using GHC 6.12.1. Thanks for any hints. Best regards, -- Tomáš Janoušek, a.k.a. Liskni_si, http://work.lisk.in/

3 3

Good US Grad schools for functional languages?
by Job Vranish 24 May '10

24 May '10

Anybody know of a good grad school in the US for functional languages? (good = has Ph.D. program that covers functional languages, type systems, correctness proofs, etc...) So far Indiana University is the only one I've found that has a strong showing in this area. A way to get into one of the awesome UK schools for free would work too :D - Job

7 9

Re: [Haskell] ANNOUNCE: Introducing Sifflet, visual functional programming language
by Henning Thielemann 24 May '10

24 May '10

Gregory D. Weber schrieb: > Introducing Sifflet -- version 0.1.5, first public release! > > Sifflet is a visual, functional programming language. Cool - when do we get something like Gem Cutter? :-) http://resources.businessobjects.com/labs/cal/gemcutter-techpaper.pdf

2 1

Re: [Haskell-cafe] Haskell SVG path parser?
by Tillmann Vogt 24 May '10

24 May '10

Am 24.05.2010 14:21, schrieb Dimitry Golubovsky: > Hi, > > Does there exist any Haskell package/library to parse the syntax of > SVG elements, esp. PATH? Hi Dimitry, If you search on hackage for svg, you find my library SVGFonts. I first thought SVGFont is a special syntax similar to SVG, but it seems to be a subset of SVG. In my opinion it would be OK to split the SVG part out into a new library. I have made some improvements to SVGFonts which I haven't uploaded (i.e. points from bezier curves lying in a raster of a certain resolution). From a short look at Hennings code I guess my code may be little bit more beginner style, but parsing of the d attribute is implemeted more fully. I have spent quite some time on a tricky function "commandsToPoints" in ReadFont.hs which is about parsing the d field and translating it into outline points. Are you looking for something like that? > > That is, the syntax of the "d" attribute (e. g. M 100 100 L 300 100 L > 200 300 z)? > > Hackage doesn't seem to have any, and Google search yields very broad results. > > Thanks. > > PS It should not be hard to write such parser, I just don't want to > reivent the wheel ;)

2 1

Haskell SVG path parser?
by Dimitry Golubovsky 24 May '10

24 May '10

Hi, Does there exist any Haskell package/library to parse the syntax of SVG elements, esp. PATH? That is, the syntax of the "d" attribute (e. g. M 100 100 L 300 100 L 200 300 z)? Hackage doesn't seem to have any, and Google search yields very broad results. Thanks. PS It should not be hard to write such parser, I just don't want to reivent the wheel ;) -- Dimitry Golubovsky Anywhere on the Web

2 3

problem with regex replace with back references
by Juan Maiz 24 May '10

24 May '10

I'm trying use subRegex to replace using back references just like the docs says: http://hackage.haskell.org/packages/archive/regex-compat/0.92/doc/html/Text… But when i try to replace with \1 i got \SOH and not "e". Can anyone help? subRegex (mkRegex "e") "hello" "\1" => "h\SOHllo" Thanks in advance -- Juan Maiz Lulkin Flores da Cunha ------------------------------------------------- === @ Softa === http://mailee.me === http://hi.im/joaomilho ------------------------------------------------- “The most exciting breakthroughs of the 21st century will not occur because of technology but because of an expanding concept of what it means to be human” John Naisbitt

2 1

A most inelegant approach to "extensible records"
by Günther Schmidt 24 May '10

24 May '10

Hi everyone, as I'm trying to design a "query language" the one thing that causes the most grieve is the apparent requirement for "extensible records". There are by now a number of solutions in Haskell for this, most prominently HList. But at the end of the day even for HList to work one needs to define singleton types, something like: data FirstName = FirstName data LastName = LastName data BirthDate = BirthDate Now this isn't much of a nit and at least it works. But overall review of "extensible records" indicates that any solution/implementation requires a tremendous amount of type-level trickery. I short, any approach I've seen so far uses elaborate type class hierarchies, functional dependencies, etc., all coding on the *type* level. I have here a very, very inelegant alternative, of which I wonder if it offers a new angle to pursue the whole thing. 1. Initial "Record" names = \fn -> fn "firstName" "lastName" "birthDate" "zipCode" Please ignore for now that all "fields" are of type String. 2. "Extension" of Record namesCity = \fn -> names fn "residence" The record (1.) gets "extended" by the field "residence" 3. Selection nameZip n _ _ _ z = \fn -> fn n z basically here we "extract" the fields firstName and residence. 4. Test toList a b = [a, b] test = (namesCity nameZip) toList Now I know this is all very very inelegant and at 1st sight totally unfeasible. But maybe we can use Conal Eliots semantic editor combinators to smoothen this out? Günther

1 0

Proof question -- (==) over Bool
by R J 24 May '10

24 May '10

I'm trying to prove that (==) is reflexive, symmetric, and transitive over the Bools, given this definition: (==) :: Bool -> Bool -> Boolx == y = (x && y) || (not x && not y) My question is: are the proofs below for reflexivity and symmetricity rigorous, and what is the proof of transitivity, which eludes me? Thanks. Theorem (reflexivity): For all x `elem` Bool, x == x. Proof: x == x = {definition of "=="} (x && x) || (not x && not x) = {logic (law of the excluded middle)} True Theorem (symmetricity): For all x, y `elem` Bool, if x == y, then y == x. Proof: x == y = {definition of "=="} (x && y) || (not x && not y) = {lemma: "(&&)" is commutative} (y && x) || (not x && not y) = {lemma: "(&&)" is commutative} (y && x) || (not y && not x) = {definition of "=="} y == x Theorem (transitivity): For all x, y, z `elem` Bool, if x == y, and y == z,then x == z. Proof: ? _________________________________________________________________ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

8 13

Calculating a value as side effect of converting list of strings into list of records.
by Eugeny N Dzhurinsky 24 May '10

24 May '10

Hello, All! I need some help to solve the following task: ================================================================================================= import Data.Map as M import Data.List as L data Pair = Pair { name, value :: String } type IxPair = (Int, String, String) type IxPairParser = Pair -> Maybe IxPair type RecordUpdateF r = String -> String -> r -> r convertPairsToRecords :: RecordUpdateF r -> IxPairParser -> r -> [Pair] -> [r] convertPairsToRecords updateRecF parsePairF initRec pairs = M.elems $ L.foldl' processWithPairs initMap pairs where initMap = M.empty processWithPairs resMap = maybe resMap (updateMapF resMap) . parsePairF updateMapF res (idx, key, value) | idx `M.member` res = M.adjust (updateRecF key value) idx res | otherwise = M.insert idx (updateRecF key value initRec) res ================================================================================================= In short, input looks like name=value pairs: pair_1_username=user pair_1_password=pass pair_1_fullname=vasya poopking The parser IxPairParser takes the pair of name=value, and extracts ordering number of the current pair, making it a triple like below (1, username, user) then convertPairsToRecords takes the triple and performs lookup in the Map for a record with given ID. Then it updates the record and places it back into the map. If no record is found - then new one is created, updated and inserted into the Map. Now, I've got the case when input contains pairs like below pair_1_lastlogin=2010-05-24 12:23 ... pair_2_lastlogin=2009-12-20 10:30 ... pair_2_lastlogin=2010-04-06 18:20 At this point I need to update the record and keep the latest date somewhere, so it will be possible to extract the latest login date among all such pairs. I can think about post-processing list [r], extract lastlogin field and simply use fold to get the oldest one. But I'd like to calculate this information during parsing of the input. And I am not allowed to change the interface of convertPairsToRecords. Can somebody please suggest how to solve the task? Probably with Writer monad, or may be State? Thank you in advance! -- Eugene Dzhurinsky

1 0

Best way to instance Fix?
by Sam Martin 24 May '10

24 May '10

Hi! I'm trying to work out the best way to generate (ideally derive) instances for the Fix type. Here's a cut down example: data Greet x = AlloAllo x x | AuRevoir deriving Show newtype Fix f = In { out :: f (Fix f) } -- deriving Show -- DOESN'T COMPILE -- workaround instance Show (Fix Greet) where show (In i) = "In " ++ show i In other words, given a number of parametised types that I can derive, say, Ord, Eq and Show for, how should I go about getting the instances for the Fix-d version of them as well? I've tried a few things, but no luck so far. Any clues? Cheers, Sam

3 3