May 2007 - Haskell-Cafe

Re: [Haskell-cafe] Currying: The Rationale
by Chad Scherrer 23 May '07

23 May '07

Is (^2) really considered currying? As I understand it, this is syntactic sugar for a "section", and might confuse the issue a bit, since it's distinct from ((^) 2). In this case we would have something like Prelude> let pow2 = ((^) 2) Prelude> map pow2 [1..10] [2,4,8,16,32,64,128,256,512,1024] I think it's also worth pointing out that currying can make point-free programming more natural. So, foldl has type Prelude> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a That this could have been defined as foldlUncurried :: ((a -> b -> a), a, [b]) -> a but then simple point-free definitions like sum = foldl (+) 0 would have to be written as sum xs = foldlUncurried ((+), 0, xs) OTOH, sometimes an uncurried version is easier to reason about. So, in some of Richard Bird's work ("Algebra of Programming" is like this, and probably at least some of his intro book) examples are uncurried, as it shows more of the algebraic structure, and allows reasoning in a product space rather than an exponential. Umm, I guess that qualifies as jargon - sorry. Chad > (^) applied to 2, produces a new function, we can map over a list: > > Prelude> let sq = (^2) > Prelude> map sq [1..10] > [1,4,9,16,25,36,49,64,81,100] > > or more explicitly: > > Prelude> let x `to` y = x ^ y > Prelude> let sq x = x `to` 2 > Prelude> map sq [1..10] > [1,4,9,16,25,36,49,64,81,100] > > -- Don

4 4

Currying: The Rationale
by PR Stanley 23 May '07

23 May '07

Hi What is the rationale behind currying? is it for breaking subroutines into pure one-to-one mappings? If f x y = f x -> a function which takes y for argument then does that mean that the second function already has value x, as it were, built into it? The syntax in Haskell is perfectly lucid and almost intuitive; unlike the underlying theory which is a bit ... top marks for the least jargoned answer. Many thanks in advance, Paul

5 5

efficient and/or lazy partitions of a multiset
by Greg Meredith 23 May '07

23 May '07

HC-er's, Find below some simple-minded code from a naive Haskeller for generating all partitions of a multiset about which i have two questions. mSplit :: [a] -> [([a], [a])] mSplit [x] = [([x],[])] mSplit (x:xs) = (zip (map (x:) lxs) rxs) ++ (zip lxs (map (x:) rxs)) where (lxs,rxs) = unzip (mSplit xs) 1. Is there a clever way to reduce the horrid complexity of the naive approach? 2. How lazy is this code? Is there a lazier way? i ask this in the context of checking statements of the form \phi * \psi |= e_1 * ... * e_n where - [| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi |], b_2 \in [| \psi |] } - === is some congruence generated from a set of relations A nice implementation for checking such statements will iterate through the partitions, generating them as needed, checking subconditions and stopping at the first one that works (possibly saving remainder for a rainy day when the client of the check decides that wasn't the partition they meant). Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

2 4

Editor
by Michael T. Richter 23 May '07

23 May '07

I have a dream. It's not a little dream. It's a big dream. I have a dream that someday I can find a UNIX/Linux text editor for Haskell hacking (and possibly two or three hundred other programming languages, although that's optional) that can give me all of the following: 1. A real GUI environment that takes into account some of the HID advances made in the past 30 years. (Emacs and Vim don't count, in other words.) 2. Good quality syntax highlighting for Haskell that includes all of the usual syntax highlighting goodies, plus: * the ability to seamlessly handle raw Haskell and both common forms of Literate Haskell; * the ability to properly highlight Haddock comments; * the ability to highlight functions and types from libraries (user-expandable) differently from local functions and types. 3. Line folding to hide and show blocks of code. 4. Code completion (user-expandable, ideally) for common library functions, type declarations, etc. 5. Easy, quick access to online documentation for said functions and declarations. 6. Good (ideally scriptable) access to external utilities for compilation, debugging, profiling, type inference, project management, etc. 7. A good plug-in system (ideally written in Haskell?) for expansion. Is there such a beast available out there somewhere? If not, is such a beast lurking in the background ready to pounce in the near future? -- Michael T. Richter <ttmrichter(a)gmail.com> (GoogleTalk: ttmrichter(a)gmail.com) I have to wonder why people think that when they can't manage local personnel within easy strangling and shooting distance, then they can manage personnel thousands of miles away that have different languages, cultures, and business rules. (Joe Celko)

26 39

Re: [Haskell-cafe] New book: Real-World Haskell!
by Alfonso Acosta 23 May '07

23 May '07

On 5/23/07, Donald Bruce Stewart <dons(a)cse.unsw.edu.au> wrote: > > Bryan O'Sullivan, Don Stewart and John Goerzen are pleased, and frankly, > very excited to announce that were developing a new book for O'Reilly, on > practical Haskell programming. The working title is Real-World Haskell. That is simply great! I've been looking forward to read a book like that for so long. > 28. Advanced Haskell: MPTCs, TH, strong typing, GADTs Existential types are a must in this chapter! even more important that TH and GADTs.

1 0

type class question
by Tim Docker 23 May '07

23 May '07

I think this must almost be a FAQ, or at least a PAQ (Previously AQ)... If I have a type class for conversion to a type X: class XType a where toX :: a -> X I can define instances for instance XType Int where toX = ... instance XType Double where toX = ... instance XType Tuple where toX = ... but not for Strings, given that they are a synonym for [Char]. Hence: instance XType String where toX = ... results in: Illegal instance declaration for `XType String' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `XType String' Is there some type class cleverness that can make this work in haskell 98? I can create a new wrapper type for strings: newtype StringWrap = StringWrap String and write an instance for that, but then I'll have to litter my code with calls to this constructor. I'm aware of the approach taken by class Show in the prelude, which adds a extra method to the class: class XType a where toX :: a -> X listToX :: [a] -> X but I believe this says that whenever we can convert a to an X we can also convert [a] to an X, whereas I only want [Char] to be acceptable. Thanks for any pointers. Tim

4 5

Re: [Haskell] boilerplate boilerplate
by Jacques Carette 22 May '07

22 May '07

Personally I would like {-# OPTIONS -fglasgow-exts -fgenerics -} module Blog.Types where family Usual = (Eq, Ord, Read, Show, Typeable) data BlogEntry = Entry EpochSeconds Name Email Title Body deriving Usual newtype Name = Name String deriving Usual newtype Title = Title String deriving Usual newtype Body = Body String deriving Usual Of course, if you're doing that, you might as well change those last 3 lines with newtype-schema NamedString = NamedString String deriving Usual instantiate NamedString with Name, Title, Body To me, that is very clear. Syntax-wise, I am sure things can be improved (but I rather like 'family', 'foo-schema' and 'instantiate', but not really the 'with'). Jacques Alex Jacobson wrote: > Consider this module for a blog entry that I will want to put in > various generic collections that require Ord > > {-# OPTIONS -fglasgow-exts #-} > module Blog.Types where > import Data.Typeable > import Data.Generics > > data BlogEntry = Entry EpochSeconds Name Email Title Body > deriving (Eq,Ord,Read,Show,Typeable) > > newtype Name = Name String deriving (Eq,Ord,Read,Show,Typeable) > newtype Title = Title String deriving (Eq,Ord,Read,Show,Typeable) > newtype Body = Body String deriving (Eq,Ord,Read,Show,Typeable) > > > It seems really unnecessarily verbose. Having to add the OPTION > header AND import Data.Typeable and Data.Generics just to derive > Typeable is a beat-down. It is even more of a beat-down to have to > add a deriving clause for every newtype to make this all work nicely. > Is there a way to make all types automatically derive everything > unless there is an explicit instance declaration otherwise? > > {-# OPTIONS -fglasgow-exts -fgenerics -fderiving#-} > module Blog.Types where > > data BlogEntry = Entry EpochSeconds Name Email Title Body > newtype Name = Name String newtype Title = Title String newtype > Body = Body String > Isn't that much nicer? > > -Alex- > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

1 0

How do I insert an element in HaXml?
by Jeremy Shaw 22 May '07

22 May '07

Hello, How do I create a HaXml filter that adds a new element as a child of an existing element. For example, let's say I have the XML document: <a> <b/> <c/> </a> How do I add a new element under <a /> so that I have the document: <a> <newElement/> <b/> <c/> </a> The following works, but it seems very hackish because I have to use the underlying HaXml data types. I think I could possibly use the filters in Text.XML.HaXml.Xtract.Combinators, but that seems like overkill for such a seemingly simple (and common?) operation. import Text.XML.HaXml import Text.XML.HaXml.Types import Text.XML.HaXml.Pretty insertNewElement = extract (\(CElem (Elem name _as cs)) -> mkElem name [mkElem "newElement" [] , const cs]) where extract :: (Content -> CFilter) -> CFilter extract f = \c -> f c undefined -- these are just helper functions to invoke my filter. But, I'll -- happily accept improvements to these functions as well ;) main = print $ document $ runFilter "<a><b /><c /></a>" insertNewElement runFilter :: String -> CFilter -> Document runFilter xmlStr cfilter = let (Document p s e m) = xmlParse "" xmlStr in case (cfilter (CElem e)) of [CElem e'] -> Document p s e' m [] -> error "produced no output" _ -> error "produced more than one output" thanks! j.

2 3

List algorithm
by Steffen Mazanek 22 May '07

22 May '07

Hello, is there an efficient algorithm that takes two positive numbers n and m and that computes all lists l of numbers 0<x<=n such that sum l = m? For instance alg 5 1 = [[1]] alg 5 2 = [[1,1],[2]] alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] ... I know that filter (\l->sum l == m) (powerSet [1..n]) would do the job, however I am looking for a more efficient approach. Help is greatly appreciated, even a google search term would be fine :-) I really hope for a polynomial algorithm although I am not very optimistic about this. Ciao, Steffen

8 11

Re: [Haskell-cafe] Ann: Emping 0.2
by Hans van Thiel 22 May '07

22 May '07

On Mon, 2007-05-21 at 14:06 -0700, Scott Cruzen wrote: > Is Emping an implementation of C4.5 or something new? No, it's new. The reduction algorithm is not based on a measure and is not a search either. It's a construction of predicate combinations, starting with singletons, that are not contradictory to known facts. The third step, following hypothesis and then falsification, is verification with observed rules. The complexity appears to be quadratic to the original rule length and also to the number of original rules, but I have yet to prove this. I believe I have proved that the algorithm produces the complete and shortest disjunctive normal form of a logical rule table. The white paper 'Deriving heuristic rules from facts' http://j-van-thiel.speedlinq.nl/dwnl/EmpingWP.pdf (21 pages) discusses the theory from examples, and an earlier wp (also available on the web site) uses some first order predicate logic and set theory. Version 0.2 also shows logical dependencies in the reduced rules and this is just a search in the original rules and in the poset of reductions. So this is not new in a theoretical sense, though I believe no other implementation has ever considered such dependencies. Regards, Hans van Thiel > > * Hans van Thiel <hthiel.char(a)zonnet.nl> [070521 05:45]: > > Hello All, > > > > Version 0.2 of Emping, a utility to derive heuristic rules from a table > > of nominal data, is available. In addition to a reduced normal form > > in .csv format, which can be read by Open Office Calc, it now also > > displays observed implications and equivalences in the reduced rules (if > > present) and ambiguities in original rules (if present). > > A bug in the response to a user typing error has been fixed and some > > code has been simplified, compared to 0.1. An online user guide is at: > > http://j-van-thiel.speedlinq.nl/emp/empug.html and the Cabal package can > > be downloaded from there, or from the HackageDB. > > > > Thanks, > > > > Hans van Thiel > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0