March 2010 - Haskell-Cafe

Fwd: [Haskell-cafe] Bytestrings and [Char]
by Alberto G. Corona 24 Mar '10

24 Mar '10

---------- Forwarded message ---------- From: Alberto G. Corona <agocorona(a)gmail.com> Date: 2010/3/24 Subject: Re: [Haskell-cafe] Bytestrings and [Char] To: Stephen Tetley <stephen.tetley(a)gmail.com> 2010/3/24 Stephen Tetley <stephen.tetley(a)gmail.com> Hi Alberto > > I rather doubt a valuable set of type classes that is suitable for all > containers exists, I'm afraid. > > If you consider containers as the containers package, the data > structures are all (?) functorial - but they have different shapes, > so e.g. a cons operation makes sense on the linear ones > (Data.Sequence, Data.List) but not on Data.Map, Data.Tree. 'cons' is > analogous to 'insert' but 'insert' exactly describes the operation on > maps whereas 'cons' doesn't, similarly 'insert' doesn't describe the > 'cons' operation on lists exactly as it doesn't indicate the position > of where it adds to the list. > Some operations like insert in list could be inefficient, some operations like cons in maps could be an inefficient hack, but at this does not means that a list can do create, insert, map , lookup faster that a Map in the case of sort lists, for example. A generalized cons applied to a Map can make less sense, but a program made for lists with occasional cons's can happen to perform better with Maps and so on. So a library with generality in mind can perform optimally in two or more different scenarios with different instances/implementations. . A genetic algoritm can have the opportunity to detect this. I think also that a complex list of class hierarchies is neither necessary nor recommended. We are not talking about mathemathical concepts. This is a performance issue. Even if a definitive class hierarchy is a problem, hopefully it may be worth to define tentative and temporal classes for performance testing purposes, that warps the common primitives with the sole purpose of executing the testing algorithm for different instance implementations, compilation flags and fusion rules. > > Now, if you partition the type classes into small groups you get over > the fact that some operations make sense on certain 'shapes' of data > structure, but there are still subtle type differences that aren't > conducive to type classes - e.g. ByteString and Data.Text aren't > functorial so map is type restricted: > > map :: (Word8 -> Word8) -> ByteString -> ByteString > > For this purpose, specific testing classes for Word8 data -with no claim to be "official" can be defined by the programmer, leaving to the library user to run the testing process for the different instances in his particular program. I know that this add extra work and that not many would do this extra level of abstraction, but perhaps this is less work than spending even more time exchanging emails, discussing low level issues, performing tests, trying to figure out what will be the most common sceniarios for wich the library could be used, testing manually what is the container that has the most performance here and now, not tomorrow for these scenarios, to worry about the obsolescence of the library for reasons not related with the library algorithm etc Also, while ListLike does provide default definitions for many ops I'm > guessing its more important for performance to redefine them, so the > defaults definitions aren't adding much. > > There might be a couple of useful new type classes waiting in the > wings, e.g a destroy one as per view in Data.Sequence, but I doubt > that a proliferation of classes will generally make programs clearer > or more efficient and it would introduce more instances of problems > that we already have with Num type class. > > class Destroy f where > destroy :: f a -> (a, Maybe (f a)) > > Best wishes > > Stephen > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

1 0

Re: [Haskell-cafe] Graphical representation of Haskell code
by Dupont Corentin 24 Mar '10

24 Mar '10

Hello! Thanks for the welcome! Ivan: Too overcome the problem of large and messy images, i propose too have a system to navigate into the code. You could zoom in and out, occulting unecessary details while zooming out. My big graphic of map (+1) could easely be summed up to: (Embedded image moved to file: pic36782.jpg) My idea is to provide an efficient system of zooming, as you can zoom in a fractal picture, showing more or less details! Such a tool, if created, could be implemented as a part of, or used by SourceGraph. In the first place i thought the GHC API would be great to infer each function's type. But indeed haskell-src-exts seems to be more appropriate as you get the structure of the program. Lyndon: Wahou this page (MockingBirds) his very interresting and funny! Mihai: That's funny we had the same idea quite the same time. I guess that idea is "in the air" and as said one contributor on your Reddit, "a well explored territory": It has major pitfalls and the reason why we heard little about that wild territory is because many explorers never returned :) By the way, i'm interrested and i could contribute on the little spare time i have. My idea is to make it as a library that display code as graphs. That library could be used for several purposes: debugging as you proposes, but also education, shows, audit (with SourceGraph), and why not construction... I think this kind of visual tool could be a "plus" in Haskell popularity. Despite not being that efficient, it is spectacular. Ronald: I agree big graphs are confusing. The big point of the project is to find or adapt an algorithm to simplify the graph and make it valuable. I'll have to make little graphics for each of your versions of map, this may be instructive to me... Stephen: I'll have a look at those interaction nets! But the home page for INBlobs seems to be down. Thank you all for you kind responses. Corentin

2 2

how to make it faster ?
by 国平张 24 Mar '10

24 Mar '10

Hi, I wrote a type program to compute fibonacci series, if the max value is big, then it becomes very slow. like take 100 fib How can I make it faster :-) >>>>>>>>>>>>>>>> fibo 0 = 0 fibo 1 = 1 fibo (n+2) = (fibo n) + (fibo (n+1)) fib :: [Int] fib = [fibo i | i <- [0..]]

3 2

Re: [Haskell-cafe] Bytestrings and [Char]
by John Lato 24 Mar '10

24 Mar '10

Hi Alberto, To some extent this already exists, it's just that nobody uses it. I believe it's the approach taken by the Edison libraries. Also the ListLike package provides the type classes ListLike, StringLike, and a few others. Neither seems to have become very popular despite having well-respected authors (Okasaki and Goerzon, respectively). Some container functions are already provided by other classes, namely Foldable, Traversable, and Monoid. The first bit, creating a tree of type classes suitable for all containers, is probably a few hours work. An automated system to determine the best implementation is significantly more difficult; I can't say if the scope would be appropriate for SoC. Best, John > From: "Alberto G. Corona " <agocorona(a)gmail.com> > > Just a dream: > -separate interface and implementation for all containers, via type classes > -develop, by genetic programming techniques + quickcheck, a system that find > the best container implementation for a particular program. > > Is that suitable for a Google Summer of Code project? > > 2010/3/23 Alberto G. Corona <agocorona(a)gmail.com> > > The question can be generalized via type classes: Is there any common set of >> primitives encapsulated into a single type class that has instances for >> Strings (Data.List) ByteStrings, Data.Text, Lazy bytestrings, Arrays, >> vectors and wathever container that can store an boxed, unboxed, packed >> unpacked sequence of wathever including chars? All of them have folds, >> heads, tails and a lot of common functions with the same name, but since >> there is not a single type class, the library programmer can not abstract >> his code when it is possible, so the library user can chose the particular >> instance for his particular problem.

6 6

really difficult for a beginner like me...
by Ivan Amarquaye 24 Mar '10

24 Mar '10

Hi everyone, this is my first posting on here and this was what drove me here and the quest to know more as i anticipate a lot of help and direction in this quite new and different environment haskell.I have this paper that i'm working on and need to solve these scenarios/ cases based on some sample codes: Scenarios/cases: 1) Allow words to be hyphenated and treat the hyphenated word as a single word (including the hyphen). 2) As for no. 2 but if the hyphen is the last character on a line treat the hyphenated word as a single word without the hyphen. 3) Treat a capitalised word (one or more capital letters) the same as lower case, i.e. only the lower case word appears in the index. 4) Treat a word ending in an ‘s’ as a plural and thus the same as the singular, i.e. only the singular appears in the index. 5) As for no. 5 but (a) treat suffix ‘ss’ as not a plural; and (b) treat the plural suffixes ‘sses’, ‘zzes’, ‘oes’, ‘xes’, ‘shes’, ‘ches’ the same as the singular, i.e. without the ‘es’, e.g. “branches” (except for 4- and 5-letter plurals with suffices ‘oes’ and ‘ches’, e.g. “floes”, and 4-letter plural suffix ‘xes’); and (c) treat the plural suffix ‘ies’ (except for 4-letter plurals, e.g. “pies”) as the singular suffix ‘y’. 6) Make the output more readable in the form of an index table. 7) Use an output file 8) Include a user-friendly menu by which the user can choose input and output file names. This is the code i'm supposed tomodify and in some cases create new functions to support.I also need some explanation as the various approaches in solving them.............................................................................................. The function makeIndex given a document produces a list of entries. Each entry is a word and a list of line numbers (for words > 4 letters) Type definitions: import Prelude -- hiding (Word) -- predefined Word hidden, so we can define ours -- type String = [Char] defined in Prelude type Doc = String type Line = String type Word = String -- our version makeIndex :: Doc -> [ ([Int], Word) ] A data-directed design considers a sequence of functions (i.e using composition operator ‘.’) to transform the document of type, Doc, into an index of type, [ ([Int], Word) ]. splitUp the document, doc, into a list of lines, [Line]. numLines pairs each line with a line number, [(Int, Line)]. allNumWords splits lines into words and line no., [(Int, Word)]. sortLs sorts words into alphabetical order, [(Int, Word)]. makeLists makes a list for each line number, [([Int], Word)]. amalgamate nos. into a list of nos. for each word, [([Int], Word)]. shorten into a list for words > 4 letters, [([Int], Word)]. makeIndex = shorten . -- [([Int], Word)] -> [([Int], Word)] amalgamate . -- [([Int], Word)] -> [([Int], Word)] makeLists . -- [(Int, Word)] -> [([Int], Word)] sortLs . -- [(Int, Word)] -> [(Int, Word)] allNumWords . -- [(Int, Line)] -> [(Int, Word)] numLines . -- [Line] -> [(Int, Line)] splitUp -- Doc -> [Line] Last -- [a] -> [a ] splitUp function splitUp :: Doc -> [Line] splitUp [] = [] splitUp text = takeWhile (/='\n') text : -- first line (splitUp . -- splitup other lines dropWhile (==’\n’) . -- delete 1st newline(s) dropWhile (/='\n')) text -- other lines Example: splitUp “hello world\n\nnext world” => [“hello world”, “next world”] numLines function: numLines :: [Line] -> [(Int, Line)] numLines lines -- list of pairs of = zip [1 .. length lines] lines -- line no. & line Example: numLines [“hello world”, “next world”] => [(1, “hello world”), (2, “next world”)] splitWords function: -- for each line -- a) split into words -- b) attach line no. to each word splitWords :: Line -> [Word] -- a) splitWords [ ] = [ ] splitWords line = takeWhile isLetter line : -- first word in line (splitWords . -- split other words dropWhile (not.isLetter && Last ==’-’) . -- delete separators dropWhile isLetter) line -- other words where isLetter ch = (‘a’<=ch) && (ch<=’z’) || (‘A’<=ch) && (ch<=’Z’) Example: splitWords “hello world” => [“hello”, “world”] allNumWords function: numWords :: (Int, Line) -> [(Int, Word)] -- b) numWords (number, line) = map addLineNum ( splitWords line) -- all line pairs where addLineNum word = (number, word) -- a pair allNumWords :: [(Int, Line)] -> [(Int, Word)] allNumWords = concat . map numWords -- doc pairs Examples: addLineNum “hello” => (1, “hello”) numWords (1, “hello world”) => [(1, “hello”), (1, “world”)] allNumWords [(1, “hello world”), (2, “next world”)] => [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] SortLs function: sortLs :: [(Int, Word)] -> [(Int, Word)] sortLs [ ] = [ ] sortLs (a:x) = sortLs [b | b <- x, compare b a] -- sort 1st half ++ [a] ++ -- 1st in middle sortLs [b | b <- x, compare a b] -- sort 2nd half where compare (n1, w1) (n2, w2) = (w1 < w2) -- 1st word less || (w1 == w2 && n1 < n2) -- check no. Example: sortLs [(1, “hello”), (1, “world”), (2, “next”), (2, “world”)] => [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] makeLists function: makeLists :: [(Int, Word)] -> [([Int], Word)] makeLists = map mk -- all pairs where mk (num, word) = ([num], word) -- list of single no. Examples: mk (1, “hello”) => ([1], “hello”) makeLists [(1, “hello”), (2, “next”), (1, “world”), (2, “world”)] => [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] Amalgamate function: amalgamate :: [([Int], Word)] -> [([Int], Word)] amalgamate [ ] = [ ] amalgamate [a] = [a] amalgamate ((n1, w1) : (n2, w2) : rest) -- pairs of pairs | w1 /= w2 = (n1, w1) : amalgamate ((n2, w2) : rest) | otherwise = amalgamate ((n1 ++ n2, w1) : rest) -- if words are same grow list of numbers Example: amalgamate [([1], “hello”), ([2], “next”), ([1], “world”), ([2], “world”)] => [([1], “hello”), ([2], “next”), ([1, 2], “world”)] Shorten function: shorten :: [([Int], Word)] -> [([Int], Word)] shorten = filter long -- keep pairs >4 where long (num, word) = length word > 4 -- check word >4 Example: shorten [([1], “hello”), ([2], “next”), ([1, 2], “world”)] => [([1], “hello”), ([1, 2], “world”)] _________________________________________________________________ Connect to the next generation of MSN Messenger http://imagine-msn.com/messenger/launch80/default.aspx?locale=en-us&source=…

6 8

derivable type classes
by Ozgur Akgun 24 Mar '10

24 Mar '10

Can a user define a derivable type class of her own? If yes, how? Cheers, -- Ozgur Akgun

4 4

Syntax programming with lexemes rather than trees?
by Stephen Tetley 24 Mar '10

24 Mar '10

Hello All Modern functional programming languages give you algebraic data types that are mighty convenient for programming with syntax trees. However, I'm working in a domain (music typesetting) where modelling syntax with trees can be problematic and I'm wondering whether I should work at a lower level - essentially a list / stream of lexemes and some notion of a context stack for processing, tracking when I'm inside a tuplet and the metrical calculation is scaled, for example. Does anyone know of any previous work that takes a "lexical" view of syntax rather than an abstract syntax tree view? Any domain is good - I can't imagine there's any prior work on music typesetting. Pointers to papers would be more digestible than code but either is fine. Similarly, implementation in any functional language is fine. Thanks Stephen

4 6

Problem with Haskell Platform website
by Dietrich Epp 24 Mar '10

24 Mar '10

There's a problem with the Haskell Platform website. I'm posting the message here because I gave up looking for contact information for the site, maybe someone here can forward the message or tell me who to forward it to? The specific page is http://hackage.haskell.org/platform/mac.html Being one of the few who still use the PPC architecture, I expect to have to build my own packages from source. Imagine my surprise when the Haskell platform uses the "Universal Binary" logo on the Mac download. Nowhere on the Mac download page does it specify an architecture. However, the binary is i386 only and not PPC. So I just wasted time downloading something I can't install on my computer. This page shows the "Universal Binary" logo: http://hackage.haskell.org/platform/ Here is Apple's "Universal Binary" page, which describes what the logo means: http://www.apple.com/universal/ It would be nice to get rid of the "Universal Binary" logo and to mark the packages as i386. --Dietrich Epp

2 1

Syntax programming with lexemes rather than trees?
by Max Rabkin 24 Mar '10

24 Mar '10

[Sorry for the accidental off-list reply, Neil] On Tue, Mar 23, 2010 at 10:43 PM, Neil Mitchell <ndmitchell(a)gmail.com> wrote: > It actually sounds like your representation has structure, but you > dislike structure because it's hard to work with. It seems to me like the data has structure, but that data is not treelike! Is a performance a collection of measures or a collection of instruments? A tree-like structure makes you choose, but in truth it is both. I'm not sure I've seen a good solution to this kind of problem in FP. --Max

3 3

Are there any web server framework ?
by zaxis 24 Mar '10

24 Mar '10

Erlang has yaws (http://yaws.hyber.org/) Scala has lift (http://liftweb.net/) Python has django (http://www.djangoproject.com/) Ruby has rails (http://rubyonrails.org/) How about haskell ? Is there any similar framework, which should be steady, powerful and easy to use, in haskell ? Sincerely! ----- fac n = let { f = foldr (*) 1 [1..n] } in f -- View this message in context: http://old.nabble.com/Are-there-any-web-server-framework---tp27926433p27926… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

8 7