- Haskell-Cafe - Haskell.org

Proper Etiquette
by Mark Espinoza 15 Oct '03

15 Oct '03

Hello: A couple of days ago I posted a question about the cgi library, which was not answered. What are appropriate courses of action for me in a case like this? Thanks. Mark

3 2

fold{l|r} and short-circuit evaluation
by Graham Klyne 15 Oct '03

15 Oct '03

I'm trying to use foldl or foldr to run a computation over a list, in such a way that only as much of the list as may be needed is actually examined. I believe the 'and' function behaves like this (e.g. see testand below), but when I use a function that performs pairwise operations on the list elementsa, it seems that I always end up constructing the entire list, even if I don't need to examine the value of each element. I guess I could try and figure out my own 2-place folding function, but this seems as if there should be a common solution. My test code is below. The tests are evaluated as: test allSame1 or test allSame2 to use a foldl- or foldr-versions of the function respectively If I comment out the indefinitely long list case (test7) in the definition of 'test', the foldl version will pass all these test cases and foldr throws an error on test6. But if I include test7, using Hugs the foldr test case returns a C stack overflow, and the foldl case silently disappears. Is there a standard method for dealing with cases like this? (I ask out of curiosity rather than need: for my real application, I am using relatively short list with quite expensive combining operations, so I think the 'foldl' variant which doesn't actually examine list elements once the result is known, will work quite well for me.) #g -- -- Spike-allsame.hs -- -- Test use of folding functions to evaluate whether all members -- of a list are the same. -- -- What I'm really interested in is whether the list gets evaluated -- beyond what is needed to obtain the desired result. -- import Maybe ( Maybe(..), isJust ) test allSame = and [ test1 allSame , test2 allSame , test3 allSame , test4 allSame , test5 allSame , test6 allSame , test7 allSame ] test1 allSame = allSame [1,1,1,1] == True test2 allSame = allSame [1,2,3,4] == False test3 allSame = allSame [1,2,undefined,4] == False test4 allSame = allSame [1] == True test5 allSame = allSame [] == True test6 allSame = allSame [1,2,undefined] == False test7 allSame = allSame (1:2:repeat 3) == False testand = and (True:True:False:repeat True) longList :: [Int] longList = (1:2:repeat 3) allSame1 :: (Eq a) => [a] -> Bool allSame1 [] = True allSame1 [_] = True allSame1 (a:as) = isJust $ foldr nextSame1 (Just a) as nextSame1 :: (Eq a) => a -> Maybe a -> Maybe a nextSame1 _ Nothing = Nothing nextSame1 a1 (Just a) | a1 == a = Just a | otherwise = Nothing {- foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) foldr nextSame (Just 1) [2,undefined,4] ..> nextSame 2 (foldr nextSame (Just 1) [undefined,4]) ..> nextSame 2 (nextSame undefined (foldr nextSame (Just 1) [4])) ..> nextSame 2 (nextSame undefined (nextSame 4 (foldr nextSame (Just 1) []))) ..> nextSame 2 (nextSame undefined (nextSame 4 ((Just 1)))) -} allSame2 :: (Eq a) => [a] -> Bool allSame2 [] = True allSame2 [_] = True allSame2 (a:as) = isJust $ foldl nextSame2 (Just a) as nextSame2 :: (Eq a) => Maybe a -> a -> Maybe a nextSame2 Nothing _ = Nothing nextSame2 (Just a) a1 | a1 == a = Just a | otherwise = Nothing {- foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs foldl nextSame (Just 1) [2,undefined,4] ..> foldl nextSame (nextSame (Just 1) 2) [undefined,4] ..> foldl nextSame (nextSame (nextSame (Just 1) 2) undefined) [4] ..> foldl nextSame (nextSame (nextSame (nextSame (Just 1) 2) undefined) 4) [] ..> (nextSame (nextSame (nextSame (Just 1) 2) undefined) 4) -} ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 5

Using field selectors in a type constructor
by Graham Klyne 15 Oct '03

15 Oct '03

I've run across a minor coding niggle on a couple opf accosions when using a type constructor with field selectors. The full code of my test case is below. The value 'test2' evaluates to True. The function that niggles me is this: [[ joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = mv12 , vbEnum = map (\v -> (v,fromJust (mv12 v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } where mv12 = headOrNothing . filter isJust . flist [ vbMap vb1, vbMap vb2 ] ]] Is it really necessary to define mv12 as a separate "where" clause here? What I'd really like to do is assign it to field vbMap, and reference that from the definition of vbEnum, but I can't figure out if there's a way to do so. Writing this: [[ joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = head . filter isJust . flist [ vbMap vb1, vbMap vb2 ] , vbEnum = map (\v -> (v,fromJust (vbMap v))) $ -- error here ^^^^^^^ boundVars vb1 `union` boundVars vb2 , vbNull = False } ]] Results in a fairly obvious type error: I'd need to have a way to say that vbMap is applied to the value under construction. Experience with Java would suggest maybe something like this: [[ , vbEnum = map (\v -> (v,fromJust (vbMap this v))) $ ]] but of course Haskell isn't Java. Does Haskell provide a way to do this, other than the use of a 'where' clause to factor out the common subexpression, as in my working code? #g -- -- spike-constructorfields.hs import Maybe ( isJust, fromJust ) import List ( union, find ) -- |VarBinding is the type of an arbitrary variable bindings -- value, where the type of the bound values is not specified. data VarBinding a b = VarBinding { vbMap :: a -> Maybe b , vbEnum :: [(a,b)] , vbNull :: Bool } -- |nullVarBinding: maps no query variables. nullVarBinding :: VarBinding a b nullVarBinding = VarBinding { vbMap = const Nothing , vbEnum = [] , vbNull = True } -- |Return a list of the variables bound by a supplied variable binding boundVars :: VarBinding a b -> [a] boundVars = map fst . vbEnum -- |Join a pair of query bindings, returning a new binding that -- maps all variables recognized by either of the input bindings. -- If the bindings should overlap, such overlap is not detected and -- the value from the first binding provided is used arbitrarily. joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = mv12 , vbEnum = map (\v -> (v,fromJust (mv12 v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } where mv12 = headOrNothing . filter isJust . flist [ vbMap vb1, vbMap vb2 ] flist fs a = map ($ a) fs -- see also monad function 'ap' headOrNothing :: [Maybe a] -> Maybe a headOrNothing [] = Nothing headOrNothing (a:_) = a {- NOT this: -- |Join a pair of query bindings, returning a new binding that -- maps all variables recognized by either of the input bindings. -- If the bindings should overlap, such overlap is not detected and -- the value from the first binding provided is used arbitrarily. joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = head . filter isJust . flist [ vbMap vb1, vbMap vb2 ] , vbEnum = map (\v -> (v,fromJust (vbMap v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } -} -- |Function to make a variable binding from a list of -- pairs of variable and corresponding assigned value. makeVarBinding :: (Eq a, Show a, Eq b, Show b) => [(a,b)] -> VarBinding a b makeVarBinding vrbs = if null vrbs then nullVarBinding else VarBinding { vbMap = selectFrom vrbs , vbEnum = vrbs , vbNull = null vrbs } where -- selectFrom bs is the VarBinding lookup function selectFrom :: (Eq a) => [(a,b)] -> a -> Maybe b selectFrom [] _ = Nothing selectFrom ((v,r):bs) l = if l == v then Just r else selectFrom bs l vb1 :: VarBinding Int String vb1 = makeVarBinding [(1,"a"),(2,"b"),(3,"c")] vb2 :: VarBinding Int String vb2 = makeVarBinding [(3,"cc"),(4,"dd"),(5,"ee")] vb12 = joinVarBindings vb1 vb2 test1 = vbEnum $ vb12 test2 = test1 == [(1,"a"),(2,"b"),(3,"c"),(4,"dd"),(5,"ee")] test3 = [test31,test32,test33,test34] test31 = vbMap vb12 1 -- Just "a" test32 = vbMap vb12 3 -- Just "c" test33 = vbMap vb12 5 -- Just "ee" test34 = vbMap vb12 0 -- Nothing ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 4

putStr
by Jose Morais 14 Oct '03

14 Oct '03

Hi, I am trying to something like f1 :: Int -> Int f1 x = f2 x f2 :: Int -> Int f2 x = 2 * x but before f2 returns its result I'd like it to print something like "The initial value is " ++ show x. How could I do this? Thank you

5 6

RE: Using existential types
by oleg＠pobox.com 14 Oct '03

14 Oct '03

Tim Docker wrote: > I wish to define a flexible report, consisting of a set of columns. > The contents of each column can be defined by mapping a function to a > row descriptor, generating a value, and then converting each value > to a string. I also wish to present an aggregate value at the bottom > of the column defined by another function. > It seems that existential types are required to get this sort of > thing to work. Is there another way? It seems there is. Here's your code: > data ColDesc rowv = forall a. ColDesc (rowv -> a) ([a] -> a) (a -> > String) > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc valf sumf fmtf) = let vals = map valf rs in (map > fmtf vals, (fmtf.sumf) vals) Here's the new code: > data ColDesc rowv = ColDesc (rowv -> String) ([rowv] -> String) > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc fmtf sumf) = (map fmtf rs, sumf rs) > rows = ["I","wish","to","define","a","report"] > mapp g f = g . (map f) > cols = [ > ColDesc (id.id) $ id.(\_ -> ""), > ColDesc (show.length) $ show.(mapp sum length), > let valf = (\s -> length s * length s) in ColDesc (show.valf) $ show.(mapp maximum valf) > ] > values = [ calculate rows col | col <- cols ] It was derived with a simple transformation: composing (rowv -> a) with (a->String) to eliminate the existential type a. It seems there is a pattern here. When we write data Foo a b = forall ex. Foo <something1> <something2> <something3> with ex unconstrained, then one of <something> must be a function F(a,b) -> ex and another something is a function ex -> G(a,b). Here F(a,b) is some expression that includes ground types, a, b -- but not ex. Indeed, otherwise we have no way to convert something into ex and to get anything out. The third something is perhaps a transformer ex -> H(a,b) -> ex. It seems therefore we are guaranteed that there is always a composition of <something>s that does not include ex. Therefore, instead of carrying original <something>, we can carry the compositions, and get rid of the existential quantification. It seems that (g.f) :: i -> o is equivalent to stating exists c. f:: (i->c) ^ g::(c->o) or, in the Haskell type language data P i o = forall c. P (i->c) (c->o) P f g I also have a nagging feeling that this approach relates to Skolemization. Indeed, Mike Gunter's transformation from > data Stat i o = -- aggregate function taking i's on input and producing o > forall s. Stat > s -- init > (s -> i -> s) -- update > (s -> o) -- result to > data Stat i o = Stat { update :: i -> Stat i o > , result :: o } looks awfully like a Skolemization, with 'Stat i o' being the Skolem function.

4 8

putStr
by Jose Morais 13 Oct '03

13 Oct '03

Hi, What I needed was actualy something more like f3 :: Int -> String f3 x = show x ++ f4 x f4 :: Int -> IO String f4 x = do putStr ("initial value is " ++ show x) return (show x) but this gives the error Type checking ERROR "teste.hs":11 - Type error in application *** Expression : show x ++ f4 x *** Term : f4 x *** Type : IO String *** Does not match : [a] Can you help me? Thank you

2 1

Re: AW: Using existential types
by Graham Klyne 13 Oct '03

13 Oct '03

At 11:25 10/10/03 +0200, Markus.Schnell(a)infineon.com wrote: >Hi Graham, > > > Instead, I replace the class instances by a single algebraic > > data type, > > whose members are functions corresponding to OO-style class methods. > >could you give an example? The code in a previous message of mine [1] was an example of sorts, though complicated by some other issues. Look for type 'DatatypeVal'. [1] http://haskell.org/pipermail/haskell-cafe/2003-October/005231.html A simpler example might be: Consider a class of values called shape, for which the following operations are defined: draw :: Shape -> Canvas -> Canvas flip :: Shape -> Shape move :: Shape -> Displacement -> Shape etc. One can imagine defining a Haskell type class with these methods, but then you get the type mixing problem noted previously. What I have found can work in situations like this is to define a type, thus: data Shape = Shape { draw :: Canvas -> Canvas , flip :: Shape , move :: Displacement -> Shape etc } then one would also need methods to create different kinds of shape, e.g.: makeSquare :: Point -> Displacement -> Shape makeCircle :: Point -> Length -> Shape etc. (Assuming appropriate type definitions for Point, Displacement, Length, etc.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Using existential types
by Tim Docker 13 Oct '03

13 Oct '03

oleg wrote: > Sorry I didn't know of that requirement. The desired sharing > can easily be introduced: That's always a risk with posting a toy example - which bits are important can be hard to tell. You are right of course about being able to introduce the sharing. FWIW, after the suggestions that I've had (thanks!), my "existential-free" example is as below. Tim type ColumnFn rowv = [rowv] -> ([String],String) column :: (rowv->a) -> ([a]->a) -> (a->String) -> ColumnFn column valf sumf fmtf rows = (map fmtf vals, (fmtf.sumf) vals) where vals = map valf rows calculate :: [ColumnFn rowv] -> [rowv] -> ([String],String) calculate cfs rows = [ cf rows | cf <- cfs ] ---- rows = ["I","wish","to","define","a","report"] cols = [ column id (\_ -> "") id, column length sum show, column (\s -> length s * length s) maximum show ] :r values = [ calculate rows col | col <- cols ]

1 0

Re: global variable
by Jose Morais 13 Oct '03

13 Oct '03

Sorry the newbie question and the insistence, but how exactly do I use map or fold applied to the infinite list to get successive integers at each time? Thank you

4 3

global variable
by Jose Morais 13 Oct '03

13 Oct '03

Hello, I need a function called, say, newItem, that when first called returns 1, the next time it is called it would return 2, then 3 and so on. How can I achieve this? Thank you

3 2