December 2008 - Haskell-Cafe

bottom case in proof by induction
by raeck＠msn.com 31 Dec '08

31 Dec '08

Dear all, Happy New Year! I am learning the Induction Proof over Haskell, I saw some proofs for the equivalence of two functions will have a case called 'bottom' but some of them do no have. What kind of situation we should also include the bottom case to the proof? How about the functions do not have the 'bottom' input such as: foo [] = [] foo (x:xs) = x : (foo xs) thank you, Raeck

4 3

Re: [Haskell-cafe] about the concatenation on a tree
by Henk-Jan van Tuyl 31 Dec '08

31 Dec '08

On Wed, 31 Dec 2008 17:19:09 +0100, Max cs <max.cs.2009(a)googlemail.com> wrote: > Hi Henk-Jan van Tuyl, > > Thank you very much for your reply! > > I think the concatenation should be different to thhe > > treeConcat :: Tree a -> Tree a -> Tree a > > the above is a combination of two trees instead of a concatenation, so > I think the type of treeConcat should be: > > treeConcat :: Tree (Tree a) -> Tree a > > instead. How do you think? : ) I tried to implement it .. but it seems > confusing.. to me > > Thanks > > Max Hello Max, The function treeConcat :: Tree (Tree a) -> Tree a cannot be created, as it has an infinite type; you can however, define a function that replaces leafs with trees, for example treeConcat' in the following module, that replaces all leaves that contains a one with a given tree: > module TreeConcat where > data Tree a = Leaf a | Branch (Tree a) (Tree a) > deriving Show > treeConcat' :: Num a => Tree a -> Tree a -> Tree a > treeConcat' (Leaf 1) tree = tree > treeConcat' (Leaf x) _ = Leaf x > treeConcat' (Branch x y) tree = Branch (treeConcat' x tree) (treeConcat' > y tree) > main :: IO () > main = print $ treeConcat' (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) > (Leaf 4)) This displays: Branch (Branch (Leaf 3) (Leaf 4)) (Leaf 2) If this doen't help you either, I need to know more about what you are trying to do. Regards, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ -- > > > On Wed, Dec 31, 2008 at 3:33 PM, Henk-Jan van Tuyl > <hjgtuyl(a)chello.nl>wrote: > >> Hi Max, >> >> A simple way to do this: >> >> module TreeConcat where >>> >> >> data Tree a = Leaf a | Branch (Tree a) (Tree a) >>> deriving Show >>> >> >> treeConcat :: Tree a -> Tree a -> Tree atreeConcat xs ys = Branch xs ys >>> >> >> main :: IO () >>> main = print $ treeConcat (Leaf 1) (Leaf 2) >>> >> >> But perhaps you want a certain ordering? Have a look at: >> >> http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/Data-Tree-… >> >> >> -- >> Regards, >> Henk-Jan van Tuyl >> >> >> -- >> http://functor.bamikanarie.com >> http://Van.Tuyl.eu/ >> -- >> >> >> --

2 2

about the concatenation on a tree
by Max cs 31 Dec '08

31 Dec '08

hi all, not sure if there is someone still working during holiday like me : ) I got a little problem in implementing some operations on tree. suppose we have a tree date type defined: data Tree a = Leaf a | Branch (Tree a) (Tree a) I want to do a concatenation on these tree just like the concat on list. Anyone has idea on it? or there are some existing implementation? Thank you and Happy New Year! regards, Max

3 2

Re: [Haskell-beginners] about the concatenation on a tree
by Thomas Davie 31 Dec '08

31 Dec '08

On 31 Dec 2008, at 16:02, Max cs wrote: > hi all, not sure if there is someone still working during holiday > like me : ) > > I got a little problem in implementing some operations on tree. > > suppose we have a tree date type defined: > > data Tree a = Leaf a | Branch (Tree a) (Tree a) > > I want to do a concatenation on these tree just like the concat on > list. > Anyone has idea on it? or there are some existing implementation? > > Thank you and Happy New Year! > How would you like to concatenate them? Concatonation on lists is easy because there's only one end point to attach the next list to, on a tree though, there are many leaves to attach things to. Here's a few examples though: Attaching to the right most point on the tree (tree data structure modified to store data in branches not leaves here) data Tree a = Leaf | Branch (Tree a) a (Tree a) concatT :: [Tree a] -> Tree a concatT = foldr1 appendT appendT :: Tree a -> Tree a -> Tree a appendT Leaf t = t appendT (Branch l x r) t = Branch l x (appendT r t) Attaching to *all* the leaves on the tree (same modification to the data structure) concatT :: [Tree a] -> Tree a concatT = foldr1 appendT appendT :: Tree a -> Tree a -> Tree a appendT Leaf t = t appendT (Branch l x r) t = Branch (appendT l t) x (appendT r t) merging a list of trees maintaining them as ordered binary trees concatT :: Ord a => [Tree a] -> Tree a concatT = foldr1 unionT unionT :: Ord a => Tree a -> Tree a -> Tree a unionT t = foldrT insertT t foldrT :: (a -> b -> b) -> b -> Tree a -> b foldrT f z Leaf = z foldrT f z (Branch l x r) = f x (foldrT f (foldrT f z r) l) insertT :: Ord a => a -> Tree a -> Tree a insertT x Leaf = Branch Leaf x Leaf insertT x (Branch l y r) | x <= y = Branch (insertT x l) y r | otherwise = Branch l y (insertT x r) Hope that helps. Bob

1 0

Re: Gitit - Encoding
by Arnaud Bailly 30 Dec '08

30 Dec '08

Hi Jeremy and John, Thank you very much Jeremy for your very detailed answer ! I checked in Gitit source and found various occurences of usage of Byte8 strings, which John as confirmed. I switched template.html to advertising encoding of iso-8859-1 and things are working ok. I setup LANG (and LC_ALL) to fr_FR.UTF-8. When I set meta tag with utf-8 encoding, things get messy. John: I checked your url and, oddly enough, characteres appears OK when I manually change page display encoding to latin-1. I came to the possibly obvious conclusion that: -gitit communicated with HApps hence the outside world in latin-1 - talk to git in utf-8 Is this the right picture ? If so, then I have part of the problem solved. Using latin-1 for input/display is annoying only for the € (euro) symbol. Regards, Arnaud BTW, my accents problem solved, I would like to work with RSS feeds so that: 1. a user could put a feed inside a page 2. gitit could produce feeds for changes/adds I have done things like that before in Java but would need some directions to incorporate it in gitit. -- Arnaud Bailly, PhD OQube - Software Engineering web> http://www.oqube.com

2 1

fedora-devshell and Haskell
by Yaakov Nemoy 30 Dec '08

30 Dec '08

Hi Folks, I spent the better part of yesterday working on some tools for doing Fedora packages for Cabal. I've put up a blog report with some preliminary explanations on how to use it, but it might be of value to regular Haskell programmers. The post can be found below. http://loupgaroublond.blogspot.com/2008/12/lazyness-and-cabal-packages.html fedora-devshell's going to be aimed primarily on managing and automating the development of haskell packages for an RPM based distro. It might be useful to other developers too, and i would like to hear if anyone finds it useful. Cheers, and Happy New Year, Yaakov Nemoy

2 1

Reading group for Programming Collective Intelligence
by Creighton Hogg 30 Dec '08

30 Dec '08

Hello Haskellers, For those of your who aren't nose-deep in Real World Haskell at the moment, I'd like to start a small group for the O'Reilly book Programming Collective Intelligence*. I think it might be very instructive to convert the examples & exercises to Haskell. I think it would be good experience for doing neat applications in Haskell & may provide opportunities for adding to Hackage if the book relies on Python libraries that we don't have an equivalent for. If anyone is interested, just e-mail me & I can work on the organization. Cheers, Creighton * http://tinyurl.com/7x4rga

2 1

instance Enum [Char] where ...
by JustinGoguen 30 Dec '08

30 Dec '08

I am having difficulty making [Char] an instance of Enum. fromEnum is easy enough: map fromEnum to each char in the string and take the sum. However, toEnum has no way of knowing what the original string was. For example, running fromEnum on the string "d" will result in 100. But when we pass 100 to toEnum, it does not know if it should treat 100 as "d" or "22" (fromEnum '2' == 50). Source so far: instance Enum [Char] where succ = undefined pred = undefined toEnum n = undefined -- what to do? fromEnum xs = sum $ map fromEnum xs

8 7

Function composition
by Oscar Picasso 30 Dec '08

30 Dec '08

Hi, I can write: *Main> let yes = not . not *Main> :t yes yes :: Bool -> Bool But not: *Main> let isNotEqual = not . (==) <interactive>:1:23: Couldn't match expected type `Bool' against inferred type `a -> Bool' Probable cause: `==' is applied to too few arguments In the second argument of `(.)', namely `(==)' In the expression: not . (==) Why? Oscar

8 9

Re: [Haskell-cafe] represent data sturcture using function
by Ryan Ingram 30 Dec '08

30 Dec '08

On Mon, Dec 29, 2008 at 4:29 AM, <raeck(a)msn.com> wrote: > Would you please give me a complete example of code that I could have more > information > on the idea? Sure, I put up an example at http://ryani.freeshell.org/haskell/gmap.hs class MapKey k where data (:->) k :: * -> * newMap :: (k -> v) -> (k :-> v) fetch :: (k :-> v) -> (k -> v) update :: k -> (v -> v) -> (k :-> v) -> (k :-> v) assign :: k -> v -> (k :-> v) -> (k :-> v) assign k v m = update k (const v) m empty :: v -> (k :-> v) empty = newMap . const with instances & associated data types: instance MapKey () where -- A single value newtype () :-> v = UMap v instance MapKey Bool where -- A value for False and True data Bool :-> v = BMap v v instance (MapKey k1, MapKey k2) => MapKey (k1,k2) where -- A "curried" map newtype (k1,k2) :-> v = PMap (k1 :-> k2 :-> v) instance (MapKey k1, MapKey k2) => MapKey (Either k1 k2) where -- sub-maps for Left k1 and Right k2 data (Either k1 k2 :-> v) = EMap (k1 :-> v) (k2 :-> v) instance MapKey k => MapKey (Maybe k) where -- Now we can build up from existing structures! newtype (Maybe k) :-> v = MaybeM (Either () k :-> v) instance MapKey k => MapKey [k] where -- Value for [] and map for (head:tail) -- -- Note that this includes a recursive ([k] :-> v) map -- in the pair map (k,[k]) :-> v data [k] :-> v = ListM v ((k,[k]) :-> v) instance MapKey Positive where -- We just convert a positive number into -- a list of Bools, then make a map of those newtype Positive :-> v = PosMap ([Bool] :-> v) instance MapKey Integer where -- Now an integer is either negative, zero, or positive. -- So we store a map for negative numbers, a zero value, -- and a map for positive numbers. data Integer :-> v = IntMap (Positive :-> v) v (Positive :-> v) The rest of the class functions are reasonably easy to derive from their type and these data types. -- ryan

4 3