[Haskell-cafe] Re: Sequencing Operations in a Monad
SevenThunders wrote: Well it certainly requires some thought here. As I see it, I now have two reasonable choices. Either I pull all my matrix operations back inside the IO monad and avoid the matrix action as a matrix variable paradigm (due to the loss of referential transparency) or I devise some way to guarantee 'safety' and use unsafePerformIO. I suppose I can use a somewhat generalized version of safety where if I can guarantee that the order of operations doesn't matter to the final output then I'm OK. In this case if I can make it so that reording the computations only reorders the locations of my matrices on the stack, but otherwise doesn't affect the contents of the matrices I think I am golden. I believe I got burned by following a nice tutorial interpretation of the IO monad as a way of carrying around an undeclared state variable, the world. But my little matrix IO variable is not just a world state with some matrix data in it, rather it appears to be a world state with a chain of unapplied function evaluations. This is due to laziness I believe. If I had a data structure that looked more like a world state with a reference to a variable in that world state, I could find a way to achieve my goals I think. I know that you have already made your decision and moved on, but I think that there is still another alternative that you can consider: make an abstract interpreter for your matrix operations. The basic idea is to use the normal Num et. al. type classes to write your matrix calculations. However, instead of actually performing the calculations it instead builds a data structure that represents the calculations. You then 'interpret' the data structure in a separate function in the IO monad. The advantage of the approach is that you can pre-process the abstract data structure to recognize intermediate matrices that can be consumed without copying and other optimizations. The other advantage is that the matrix math itself doesn't need to be in the IO monad, only the interpretation, so you can use all the functional goodness when writing the matrix operations. I was going to whip up a small example, but I am pressed for time. So here is a post from Oleg that shows the idea. http://www.haskell.org/pipermail/haskell/2007-January/019012.html As usual his post is mind-expanding and probably a bit of overkill for your problem, but I was the best I could come up with, google was not my friend. You might have better luck (try higher order abstract syntax and abstract interpretation and go from there) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I'm stuck in my thought experiment
Levi Stephen wrote: Al Falloon wrote: This code seems to indicate that you want to be able to extend the widget types without changing this source file. This is a good goal, but it may not be worth the extra complexity. Ideally, I'd like Widgets to be added through hs-plugins or similar. That is a ideal goal though, not a necessity. Also, this looks a lot like the Composite pattern from OO. A rule of thumb that I use is: if I would do this with inheritance in OO, I probably want a variant in FP. Since Composite depends on the inheritance of the composite object type, I would probably look to use a single data type with multiple constructors for the different compisites like the Widget type above. Interesting. I've been curious how OO concepts can map to FP, as most specs (consider stuff like DOM) seem to be written with OO implementaitons in mind. This is a very interesting discussion that could be its own text book (or flame war) as far as I can tell, the only answer everyone agrres on is it depends. After that it gets a little hairy. For me, I find that the best method is to just come at the problem fresh using an FP approach, and don't worry about 'mapping' the concepts. If I wanted to develop the widgets themselves separately from the layout, I would probably do something like this: class Widget a where render :: a - Html bbox :: a - Size type Layout = forall a. Widget a = Widget a | Rows Spacing [Layout] | Columns Spacing [Layout] | Grid Spacing [[Layout]] type Page = Page String Layout renderLayout :: Layout - Html renderPage :: Page - Html I'm unsure this gives what I'm after. I'm trying to have layouts consist of Widgets (e.g., header images, common menu), and as pages also consist of Widgets it seems like they can be modelled using a common type/construct. Well if you want to abstract over the layout too, you can just add instance Widget Layout where render = renderLayout bbox = ... But just because you can, doesn't mean you should. I don't know the full details of your design, but what do you gain by allowing the layout to intermingle with the widgets? Is worth the extra complexity? If you treat layout as just another widget then it becomes harder to answer specific questions about the page layout because you have less information in your tree. So you want some sort of wildcard element that can be substituted in later? Maybe I am misunderstanding your requirement, but if thats the behavior you want, you should check out the term-level evaluators for lambda calculus for inspiration on substitution, but I expect your requirement may be simpler than that. I'm thinking a BlankWidget or ReplacableWidget is a fairly simple option. They could be named for the case of multiple replacements, and have a method similar to -- src - replacements- result replaceWidgets :: Widget - [(String,Widget)] - Widget which replaces all ReplacableWidgets in the source Widget with those specified. Would you happen to have some links on the evaluators for lambda calculus you talk about? I'm not as familiar as I should be with lambda calculus They are surprisingly hard to find! It must be one of those things that is so ingrained that no-one thinks to write it down. Anyway, the closest I could find to what I meant is the Interpretive Haskell programmer heading in The evolution of a Haskell programmer http://www.willamette.edu/~fruehr/haskell/evolution.hs However, now that I look at your example again, I may have been too quick to answer with LC evaluator! because your language only has substitution and not abstraction (defining functions) so you don't have much of the complexity to contend with. The obvious implementation of replaceWidgets will probably work fine for you. It might be simple to have a PlaceHolderWidget. Then insertions of the child page content happens at each of those widgets. This just gets trickier if I start considering multiple extension points for child pages and what happens when the layout/parent page changes. This is why I'm thinking I may be going along a bad path here. Exactly. With multiple substitutions you get into issues of naming, so thats why looking at lambda calculus evaluators would be the right inspiration, but I think it may be more complicated than you need. The zipper approach might be easier. I think I will try and investigate both approaches. I'm after the process here, rather than the end result Good luck. You can learn a lot just by lurking on the cafe and reading some of the better blogs. The papers are also good reading, I have a rule of 2 if I have heard the title come up twice, I read it. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I'm stuck in my thought experiment
Levi Stephen wrote: Hi, Apologies for a long post that may not be totally clear. I was thinking through a problem and how the data might be represented in Haskell. I'm now stuck and frustrated. Now, I'm not even sure whether I'm on the right track (I might still be thinking too OO). Suggestions/ideas would be much appreciated. I was imagining a drag and drop web page designer. There are a bunch of Widgets (e.g., BlogWidget, TextWidget, MenuWidget, etc) that the user can place on the page. Along with these are layout/container widgets (e.g., ColumnLayoutWidget) that can contain other widgets. I'm looking at a data structure that would allow this to be represented in Haskell, so I'm keeping in mind that these won't be written in code, but generated on the fly somehow (e.g., from a database or file). Maybe I am misunderstanding your requirements, but it seems to me that the simplest solution would be best in this case: data Widget = BlogWidget [Article] | TextWidget String | MenuWiget Menu | Rows Spacing [Widget] | Columns Spacing [Widget] You can also add a type parameter if you want to be able to carry around extra metadata about pages, or you could even parameterize the Article and Menu types if you want to be able to extend them separately or if you want to ensure your layout algorithms don't depend on widget contents by keeping their type abstract. So, my thoughts were along the lines of something like: class Widget a where render :: a - Html -- A page has a title and a Widget. -- I know this isn't valid Haskell, but I'm not sure how to specify what I -- want here. (existential types?) data Page = Page String Widget data TextWidget = TextWidget String instance Widget TextWidget -- An example layout widget data ColumnLayoutWidget = ColumnLayoutWidget [Widget] instance Widget ColumnLayoutWidget ... etc... So, entire pages might be represented something like: Page Main (ColumnLayoutWidget [MenuWidget, TextWidget mainPageText]) Page About (ColumnLayoutWidget [MenuWidget, TextWidget aboutPageText]) This code seems to indicate that you want to be able to extend the widget types without changing this source file. This is a good goal, but it may not be worth the extra complexity. Also, this looks a lot like the Composite pattern from OO. A rule of thumb that I use is: if I would do this with inheritance in OO, I probably want a variant in FP. Since Composite depends on the inheritance of the composite object type, I would probably look to use a single data type with multiple constructors for the different compisites like the Widget type above. If I wanted to develop the widgets themselves separately from the layout, I would probably do something like this: class Widget a where render :: a - Html bbox :: a - Size type Layout = forall a. Widget a = Widget a | Rows Spacing [Layout] | Columns Spacing [Layout] | Grid Spacing [[Layout]] type Page = Page String Layout renderLayout :: Layout - Html renderPage :: Page - Html Where I get stuck, is I want to extract layout information into a parent page. This would allow global changes such as adding a header image to the above pages to be done once only. By making the layout type separate from the widgets themselves, it allows you to examine the layout and do any transformations you want without having to know anything about the widgets. So I want to be able to have something like: layout = Page Main (ColumnLayoutWidget [MenuWidget, ??? ]) mainPage = ChildPage layout [TextWidget mainPageText] aboutPage = ChildPage layout [TextWidget aboutPageText] So, each page is it's layout/parent page, with additional widgets inserted/added. So you want some sort of wildcard element that can be substituted in later? Maybe I am misunderstanding your requirement, but if thats the behavior you want, you should check out the term-level evaluators for lambda calculus for inspiration on substitution, but I expect your requirement may be simpler than that. The issue becomes, given a parent page and the customized content for the child page, what is the best way to insert the customized content at the right point? Might a tree like structure be useful? But, how do you work out where in the tree child content gets added? Store a traversal with each sub tree of child page content that basically says 'insert here'? This is probably a good use for a zipper (a kind of functional iterator). http://en.wikibooks.org/wiki/Haskell/Zippers that way you can pass around a value that means right here, and its clear where the substitution will happen. Another good zipper war story is from xmonad: http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17 It might be simple to have a PlaceHolderWidget. Then insertions of the child page content happens at each of those widgets. This just gets trickier if I start considering multiple extension
[Haskell-cafe] Re: defining last using foldr
Kurt Hutchinson wrote: On 8/15/07, Alexteslin [EMAIL PROTECTED] wrote: I am really sorry, but i still can't define the function. The chapter the exercise is in precedes algebraic types or Maybe a types. And is seems that must being easy to define. I answered some exercises on using foldr such as summing for example, but this one i am trying: myLast :: [Int] - Int myLast (x:xs) = foldr (some function) x xs. With summing as i understood foldr goes through the list and sums up by (+) operator and one argument like 0. Like: foldr (+) 0 xs I don't think you can do it directly using just foldr. However, you can use foldr to build up a function that, when applied to the list, will evaluate to the last element. foldr will be acting like a function composition engine that evaluates to a function to process the list. Something like this? (spoiler warning) http://hpaste.org/2283 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] The problem with abstraction (Was: monte carlo trouble)
Chad Scherrer wrote: I'm starting to think the power of abstraction is a blessing and a curse. Haskell's abstraction mechanisms are so powerful that it's generally possible to come up with a way to solve a given problem elegantly and efficiently. On the other hand, if a problem isn't so well studied, the bulk of the work is in finding the right abstraction, which forces generalization beyond what would otherwise be needed (though it'll be easier the next time!). I agree with you, which is why I especially liked this post[1] by Claus Reinke that shows how you work from the obvious brute-force code and apply small transformations to come up with the beautiful abstracted code. [1] http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/26066 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pattern matching articles/explanations
Ian Duncan wrote: Hello everyone, I've been working on improving my Haskell knowledge, and in doing so, I have read a little about as-patterns as well as some form of pattern that uses ~ that I don't really understand. I suspect there are even more lesser-known pattern matching expressions than just these, but I don't have the stamina to decode the Haskell 98 Report. Are there any articles anyone is aware of, or anything in the Haskell wiki that covers the built-in pattern matching facilities pretty comprehensively? I've looked in the Haskell wiki myself, but information on different pattern matching abilities seems rather scattered and I'm not entirely sure what I should be looking for. http://haskell.org/tutorial/patterns.html That is the pattern section from A Gentle Introduction to Haskell. It should be a lot more accessible than the report. As to the specific reference: the ~pat is called an irrefutable pattern, which is an odd name because its primary purpose is to make the pattern lazy. For instance: f ~(Just x) y z = if something_complicated y then x else z In this case, the first parameter is not evaluated until x is demanded. In particular, unless (something_complicated y) is true it will not be demanded at all. The reason is that its called irrefutable is that it always succeeds (which could lead to pattern match failure at run-time) because you can't check the pattern until you evaluate the parameter. For our particular example, that means that (f Nothing foo bar) will still match, and if (something_complicated foo) is true, then you will get a pattern match failure at runtime when x is demanded. However, this is really useful if you only have one constructor, because it lets you deconstruct the value via a pattern and preserve the laziness. As another piece of trivia. Let bound patterns are already lazy, so you never need ~ in an outer pattern of a let. I.e. let Just x = foo is the same as let ~(Just x) = foo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Polymorphic variants
The proposal that I like the most is this one: Open Data Types and Open Functions http://lambda-the-ultimate.org/node/1453 However, it doesn't readily admit using the variants as overlapping enumerations like John suggested in a previous thread: http://article.gmane.org/gmane.comp.lang.haskell.cafe/23362 In fact it doesn't really support structural sub-typing at all (the way that polymorphic variants in Ocaml do), but it does support independent extension (which PV's don't do). Dan Doel wrote: P.S.: Some papers: http://www.cse.ogi.edu/PacSoft/publications/2000/extensiblerecords.pdf http://research.microsoft.com/users/daan/download/papers/scopedlabels.pdf The second actually discusses all the operations on variants and whatnot. The first just mentions that it's a related topic. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Interval Arithmetics
Mitar wrote: Hi! First, disclaimer: everything I know about interval arithmetics comes from this video: http://video.google.com/videoplay?docid=-2285617608766742834 The discussion in the implementation of the Boost Interval Arithmetic Library is also useful. http://www.boost.org/libs/numeric/interval/doc/interval.htm I would like to know if there is any implementation of interval arithmetics in Haskell? I would like to play a little with that. I checked the web and the straightforward approach I found: http://cs.guc.edu.eg/faculty/sabdennadher/Publikationen/paper-wflp99.ps.gz has from my point of view invalid implementation. For example, lower bound in the sum should not be just calculated as the sum of lower bounds of summands. It should return the greatest representable number which is smaller or equal to the exact value of the sum. With just boldly making a sum we ignore any errors we could introduce and this is somehow against the idea of interval arithmetics. Correct. And as it is said at the end of the talk, a system behind interval arithmetics should do a lot of work to make those intervals as small as possible while still correct and counting in all the errors we accumulated. I think a strict-typed and lazy language like Haskell would be a good place to implement this. But I would like to know if this would be possible to do from the language itself, without making changes to the compiler and/or runtime itself? Because, for example, a good implementation should reformulate equations at the runtime accordingly to exact values it wants to compute them on. For intervals of floating point numbers you will need to gain access to the FPU rounding modes for the machine (see some discussion here http://www.boost.org/libs/numeric/interval/doc/rounding.htm). I don't think that that is provided in the basic libraries so you would need to use the FFI to get it from C. And proper rounding isn't available on all platforms. For unbounded values defined in Haskell (like Integer and Rational) you need to provide round-down and round-up versions of operations that won't produce exact answers (like division on Integer and sqrt on Rational). Probably some sort of clever type-class setup could be used to provide rounding functions for intervals (the same way Ix does clever indexing for Array). Has it been done already? Sorry, not that I know of. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Very freaky
This is the best intro to category theory I have ever heard. I finally
understand. Thank you.
Dan Piponi wrote:
I thought I'd dive in with a comment to explain why category theory is
an important subject and why it often crops up in Haskell programming.
The key thing is this: in many branches of mathematics people draw
what are known as commutative diagrams:
http://mathworld.wolfram.com/CommutativeDiagram.html
So what do these diagrams represent? The letters at the 'vertices'
(known as objects) often represent sets and the arrows represent
functions. But in different branches of mathematics the same diagrams
appear with the objects and arrows having a quite different
interpretation. For example you could use a diagram like 1 - 2 to
mean 12. Or you could use X - Y to mean X implies Y. Or in {1,2} -
{4,5,6} the arrow might mean containment and so on. But here's a
remarkable fact: you can often take a definition in one branch of
mathematics and write it diagrammatically. You can then reinterpret
that diagram in a different branch of mathematics as different
definition. Sometimes the new definition isn't interesting, but often
it is. So now you can define things in multiple branches of
mathematics at the same time. It gets better. Statements of theorem
can also sometimes be written in purely diagrammatic language so a
theorem that holds in one branch of mathematics turns out to be an
interesting theorem in another. Sometimes the entire proof can be
written diagrammatically meaning you can solve problems in different
branches of mathematics at the same time. This whole
'multidisciplinary' subject is known as Category Theory.
To a good approximation (and there is a certain amount of choice over
which approximation you pick) Haskell also forms a category. The
objects are types and the arrows are functions. But as I've also
hinted above, objects can represent propositions and arrows can
represent implication. So that suggests theorems about logic might
carry over to theorems about Haskell. They do, as has been mentioned
in another thread. But that's a special case of a much wider
phenomenon where constructions in different parts of mathematics can
feed into Haskell.
So knowing category theory can help you to bring to bear mathematical
knowledge from other fields when writing Haskell code. A big example
of that payoff has been the notion of a monad. But there are many
more.
It also works the other way too. As you acquire a grasp of Haskell you
get insight into other parts of mathematics and computer science, even
if you don't yet know it! Haskell has certainly helped me this way.
(And I should confess that this is one of my primary motivations for
learning it.)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: I just don't get it (data structures and OO)
Phlex wrote: Christopher Lane Hinson wrote: Where InsidenessMap a b c represents a relationship where b's are inside a's, and b's have a state of c. Then, you need to declare a separate InsidenessMap for each possible relationship, but this ensures that you'll never put a galaxy inside a solar system. Or you can make 'a' be a reference to any type of object; there are options. Ketil Malde wrote: Identity can be emulated by relatively straightforward means: store all planets in a Map indexed by something that is useful as an identifier (i.e. stays constant and is unique), and have a Galaxy keep a list of identifiers. So basically you guys are saying I should rethink the data structure into a relational model instead of sticking to the OO model... I think i could do this pretty easily. a table would be a map of id to instance ...then another map for foreign keys, or maybe just as a member of each data Is the relational model a better fit than the object model for functional programming ? Of course it depends on what you are doing, but I actually have never needed to encode a relational model like this, even when I have deeply nested structures. I find that my usual solution involves doing my transformations on the data structure all at once. By that I mean that instead of performing a number of steps from the root of the data structure, I do all the operations in one pass. To keep the algorithms decoupled I usually end up passing the operations to perform as an argument. Higher-order functions are your friend. Because Haskell is lazy I don't really worry about doing too much and if I really need it, I can use the result as part of the transformation (its like recursion, but with values). Between laziness and HOF I rarely need any kind of state. Its not directly related to your question, but I found the iterative root-finding and differentiation examples in Why Functional Programming Matters [1] to be eye-opening about the functional way because they are algorithms that are almost always described as stateful computations, but are shown to be very elegant in a pure functional implementation. [1] http://www.math.chalmers.se/~rjmh/Papers/whyfp.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hardware
Bulat Ziganshin wrote: it seems that now we move right into this direction with GPUs I was just thinking that GPUs might make a good target for a reduction language like Haskell. They are hugely parallel, and they have the commercial momentum to keep them current. It also occurred to me that the cell processor (in the Playstation 3) might also be a good target considering its explicitly parallel architecture. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Implementing Mathematica
Jon Harrop wrote: On Wednesday 30 May 2007 22:15:55 Andrew Coppin wrote: Note that (as I understand it) GHC implements Haskell's Integer type using the GMP. And for some reason or other, they want to remove this feature... Arbitrary precision integers are quite a performance burden and they are rarely used. I would not expect a language that is trying to be efficient to impose arbitrary precision integers (or floats). In Haskell, Int gives you the standard signed, fixed size integer for your machine, and Integer gives arbitrary precision integers. Int8, Int16, ... provide signed ints of a known size, and Word8, Word16 give the unsigned. They are all instances of Num, so integer literals will be whatever type is needed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous expression problem. Has there been any work on extending Haskell's type system with structural subtyping? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Has anyone looked into adding subtyping to Haskell?
Mark T.B. Carroll wrote:
I don't know what the infamous expression problem is, nor am I
familiar with polymorphic variants or structural subtyping, but have you
looked at the Data.Generics.* stuff and Scrap Your Boilerplate papers?
They may be relevant.
The expression problem is a new name for an old problem, basically
being able to extend a data type and functions over the data type in
seperate modules with no knowledge of each other. Here is a link to (I
think) the original description:
http://www.daimi.au.dk/~madst/tool/papers/expression.txt
Structural subtyping is something like duck typing in dynamic
languages, but checked at compile time. For records, it means that if
you only access two labels then the function will work on any record
that has those labels with those types, even if it may have more labels.
For variants (or sum-types, or tagged unions, or whatever they are
called in Haskell) it means that if your function can handle certain
cases, then it can also handle values that range over less cases. So in
pseudo-Haskell with imaginary subtyping:
data Vertical a = U a | D a
data Horizontal a = L a | R a
data Direction a = #Vertical a | #Horizontal a -- borrowing ocaml
syntax: this means that Direction shares constructors with Vertical and
Horizontal
getData :: Direction a - a
getData (U a) = a
getData (D a) = a
getData (L a) = a
getData (R a) = a
getLeftStick :: IO (Vertical Int)
getRightStick :: IO (Horizontal Int)
main = do { accel - getLeftStick; print (getData accel) }
So getData doesn't care that accel is Horizontal and not Direction
because Horizontal is a sub-type of direction. Of course, in this syntax
since you named the subtyping relationship its more technically nominal
subtyping (like in traditional static OO languages) not structural
subtyping (which figures out the subtype relationship from the structure
automatically, so if we just reused the U,D,L, and R constructors in
Direction).
I have looked into SYB briefly. I will probably end up using it to keep
the amount of code to a minimum, but it won't save me from having to
define a different data type for each version of the AST if I want to
preserve type safety.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
apfelmus wrote: Al Falloon wrote: OCaml has been getting a lot of mileage from its polymorphic variants (which allow structural subtyping on sum types) especially on problems relating to AST transformations and the infamous expression problem. Has there been any work on extending Haskell's type system with structural subtyping? There's OO'Haskell but I don't know much about it. The problem with subtyping is that it renders type inference undecidable and is more limited than parametric polymorphism. It's more like a syntactic sugar, you can always explicitly pass around embeddings (a' - a) and projections (a - Maybe a'). I can see how nominal subtyping would make type inference a pain, but I'm pretty sure its solvable for structural subtyping because the inference algorithm can simply grow the type as it unifies the different terms. I think this paper describes how they pulled it off for OCaml: http://citeseer.ist.psu.edu/garrigue02simple.html Its true that subtyping can be considered syntactic sugar, but its the same sort of syntactic sugar as typeclasses, which are pretty popular. In fact, the mapping you suggest is so close to the mapping of typeclasses that it suggests some sort of convenient subtyping library using typeclasses might be possible. Has anyone looked into this? Is that what Data.Typeable provides? What is the canonical solution to the expression problem in Haskell? What techniques do Haskellers use to simulate subtyping where it is appropriate? I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). For this use case, there are some techniques available, mostly focussing on traversing the AST and not so much on the different data constructors. Functors, Monads and Applicative Functors are a structured way to do that. S. Liang, P. Hudak, M.P. Jones. Monad Transformers and Modular Interpreters. http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html C. McBride, R. Paterson. Applicative Programming with Effects. http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf B. Bringert, A. Ranta. A Pattern for Almost Compositional Functions. http://www.cs.chalmers.se/~bringert/publ/composOp/composOp.pdf Thank you, I will definitely look through those. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Thomas Schilling wrote: I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Proper subtyping or at least extendable ADTs would be nicer, but you can have type-checked progress flags using phantom types, e.g.: snip I thought that phantom types might be a solution, but how to you statically ensure that the AST has only the constructors that are appropriate for each phase? GADTS maybe. Constructors allowed in all phases, or in just one can be encoded easily enough. But then how do you encode a constructor that can be in two out of three phases? Maybe two phantom types? It all starts getting a little hairy. I will have to go through the papers that the others have provided to see if someone has already explored this direction. I have an inkling that there is a good idea here, it just might take some time to tease it out. Thanks for the replies. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Jon Harrop wrote: On Thursday 31 May 2007 15:36:13 Al Falloon wrote: I bring this up because I have been working on a Scheme compiler in Haskell for fun, and something like polymorphic variants would be quite convinent to allow you to specify versions of the AST (input ast, after closure conversion, after CPS transform, etc.), but allow you to write functions that work generically over all the ASTs (getting the free vars, pretty printing, etc.). Although this is the theoretical justification for OCaml's polymorphic variants, it is not their most common use. They are more commonly used to implement overlapping enumerations (see LablGL), to avoid sum type declarations with short scope (e.g. [`Some|`None| `Maybe] inside a single function) and when sum types keep changing during development. I kind of saw the overlapping enumeration case as just a common special case of the AST problem. I can't think of a lightweight way to encode overlapping enumerations in Haskell. If someone can come up with one, it would probably shed some light on the right direction for the AST problem. The other uses of PV, I hadn't been aware of, but it makes a lot of sense. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Has anyone looked into adding subtyping to Haskell?
Stefan Holdermans wrote: Al, Has there been any work on extending Haskell's type system with structural subtyping? Koji Kagawaga. Polymorphic variants in Haskell. In Andres Loeh, editor, Proceedings of the 2006 ACM SIGPLAN Workshop on Haskell, Portland, Oregon, USA, September 17, 2006, pages 37--47. ACM Press, 2006. [1] What is the canonical solution to the expression problem in Haskell? Not canonical but Loeh and Hinze have proposed open data types: Andres Loeh and Ralf Hinze. Open data types and open functions. In Annalisa Bossi and Michael J. Maher, editors, Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, July 10--12, 2006, Venice, Italy, pages 133--144. ACM Press, 2006. [2] Thanks for the pointers. I will definitely be reading these papers. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Parsec beginners problem
Jim Burton wrote: After posting I realised the difference between parsing (a) | (b) and parsing a | aa ... so Parsec doesn't do the latter well or at all? It should do (try aa) | a just fine. If you mean a general sequence of as then (many1 (char a)) should do. The Morse Code problem is a little harder though. To handle the ambiguity you may need to simultaneously consider possible parses of the dots and dashes. I suggest you look into using the List monad. As for the actual parsing of the dots and dashes, Parsec may be overkill. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: fftw bindings
Magnus Therning wrote: On Thu, Apr 19, 2007 at 09:20:36 -0700, David Roundy wrote: On Thu, Apr 19, 2007 at 05:37:05PM +0200, Fawzi Mohamed wrote: I was wondering if someone had fftw bindings for haskell, or if I should roll my own. Not that I'm aware of, but if you roll your own, please make them public, as I'll be interested in fftw bindings before long. For us less knowledgable, what's fftw? Fastest Fourier Transform in the West. http://www.fftw.org/ Its cool, they use generative programming: an OCaml program generates codlets in C that can be composed and tuned to the specifics of your machine, then compiled into a blazingly fast FFT/DFT library. /M (curious) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Takusen - error handling and DBM monad
Bayley, Alistair wrote: Al Falloon wrote: what does withSession return if there is a DBException? Well, whatever the handler returns, same as with any other exception handler. Note that this must have the same type as whatever withSession returns, and this constraint is enforced by the type of catch/catchDB: Sorry, I wasn't clear. What does it return when there is an uncaught exception? It sounds like it raises an exception in IO. Is this correct? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Boost equivalent
Boost.Python is for extending Python with C++, or embedding Python in C++. This is especially useful because it allows you to use Python as an extension language for a C++ program. Presumably Boost.Haskell would be for integrating Haskell code with C++, which would of course be useful, but the main use case (an embedded extension language) that draws people to Boost.Python isn't as much of a draw for Haskell because of the compilation phase. On the other hand, I suppose you could always integrate a Haskell interpreter like Hugs, or even go the HsPlugins route and dynamically load a compiled module, but the fit doesn't seem as natural as it does with a latently typed scripting language. There are also technical problems that are hard to overcome. Extending Python is mostly done in C, so a C++ library to add some nice sugar is a good fit. Haskell, OTOH, embeds C programs via its FFI. There doesn't seem to be any way to export functions and value from C++ to Haskell, but instead the C++ code must import from Haskell. All the heavy lifting is done on the Haskell side, so there isn't as much opportunity to write a slick C++ library. This could change if someone made a version of Hugs that can be linked in as a library with a documented C API for evaluating Haskell code and mucking with Haskell values. But I don't think its much of a priority right now :) -- Alan Falloon Alexy Khrabrov wrote: One of the great strengths of Python is Boost.Python. Practitioners say it's a major advantage of Python over Ruby, for example. So the question is not whether there's a Boost in Haskell -- C++ and Haskell are too different for it to have much meaning -- but whether there's or going to be a Boost.Haskell? Cheers, Alexy On Feb 1, 2007, at 5:03 AM, John Ky wrote: Does the Haskell community have an equivalent to C++ community's Boost project with the aim of writing libraries for the eventual inclusion into Haskell? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: State of OOP in Haskell
Bulat Ziganshin wrote: Hello Al, Tuesday, January 30, 2007, 6:01:16 PM, you wrote: Design of functional programs is very bottom-up. The general plan is to identify the primitives for your domain and embed them in the language, oh, really? may be i'm using Haskell in OOP way? :) i strongly prefer to use top-down style for application programming - i.e. i solve problem introducing auxiliary functions, then fill up these functions and so on recursively i use bottom-up style for library development, though, adding more and more higher-level functionality as library evolves The method I use is actually more of a meet-in-the-middle. Its hard to know what your primitives are unless you know what you are trying to do. I find that the best approach is to try and write my program using whatever constructs feel natural for the domain, then see if I can define the domain constructs starting with the smallest, most obvious ones and combining them into the more complex nuanced constructs needed to solve my actual problem. Usually some tweaking is required to get a nice fit. Writing usable software is more craft than science. The OOP community has contributed a lot to the craft of programming. There are many concepts that have been refined by them that IMHO can be applied more easily in a functional style. IMO the major driving principle of good software design (OO, FP, or otherwise) is Once-And-Only-Once (http://c2.com/ppr/wiki/WikiPagesAboutRefactoring/OnceAndOnlyOnce.html). If you stick to OAOO, then no matter where you start you tend to converge toward a good solution(*). (*) However, depending on where you start OAOO does not always give the same good solution. I find that interesting. To me that implies that the solutions from different approaches form a Pereto optimal set (http://en.wikipedia.org/wiki/Pareto_efficiency) of the possible solutions, and that each approach buys you some sort of advantage at the expense of another. -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Takusen - error handling and DBM monad
Paul Moore wrote: Now, I can protect my query with something like main = do withSession (connect ... ... ...) ( do catchDB (do -- simple query, returning reversed list of rows. r - doQuery (sql select username from all_users) query1Iteratee [] liftIO $ putStrLn $ show r ) catcher ) So far, so good. The syntax is messy, but a little refactoring should fix that. But this doesn't catch errors in the connect call. Wrapping the withSession in catchDB doesn't work, as withSession is in the IO monad [1], not the DBM one. But using catch with catcher doesn't work, as that expects an error handler in the IO monad, but catcher is in the DBM monad. You can catch exceptions in the IO monad using 'catch' from the prelude: http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Acatch Unfortunately, you will have to write another error handler though, because the catch expects the handler to have type (IOError - IO a) instead of (DBException - DBM ...). Using both catch and catchDB should let you handle all the errors. BTW, what does withSession return if there is a DBException? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: State of OOP in Haskell
Alexy Khrabrov wrote: Well, I'm thinking in terms of OOD/OOA/OOP -- Design, Architecture, Programming. That's about the only way to model a bog system. Say I have a stock market model -- I'll have a database of tickers, a simulator to backtest things, a trading strategy, etc. Do Haskell modules provide enough encapsulation to design a system in terms of them? What are the design/architecture units in Haskell if not OO-based? Design of functional programs is very bottom-up. The general plan is to identify the primitives for your domain and embed them in the language, then solve your problems using those primitives. Evolving your primitives and program concurrently as you get a better understanding of the problem/solution. A good intro to this kind of programming is 'On Lisp' by Paul Graham (http://www.paulgraham.com/onlisp.html). Of course, he is using Lisp instead of Haskell so many of the concrete techniques for implementing this method are different[*]. However, the first section of the book that talks about how you build something on Lisp is equally applicable to building software on Haskell. I expect that in your domain, the primitives are things like: currency, time series data, trades, strategies, and so on. The primitive operations would let you perform a trade, back-test a strategy and so on. Since it is close to your chosen domain, I highly recommend you look at http://research.microsoft.com/~simonpj/Papers/financial-contracts/contracts-icfp.htm [*] On Lisp makes heavy use of macros in Lisp, which have no analog in Haskell, but can usually be substituted for lazy-evaluation and/or monads -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: proposal: HaBench, a Haskell Benchmark Suite
Kenneth Hoste wrote: The idea is to gather a bunch of programs written in Haskell, and which are representative for the Haskell community (i.e. apps, libraries, ...). A While ago I tried to write a Haskell version of John Harrops ray-tracer benchmark (http://www.ffconsultancy.com/free/ray_tracer/languages.html) but the performance was not very good (the OCaml version I based it on was at least 10x faster). I would be happy to contribute my code to the benchmark suite if you are interested. Perhaps someone can point out obvious speed-ups that I missed while trying to improve the performance. -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: proposal: HaBench, a Haskell Benchmark Suite
David Roundy wrote: On Fri, Jan 26, 2007 at 10:17:28AM -0500, Al Falloon wrote: Kenneth Hoste wrote: The idea is to gather a bunch of programs written in Haskell, and which are representative for the Haskell community (i.e. apps, libraries, ...). A While ago I tried to write a Haskell version of John Harrops ray-tracer benchmark (http://www.ffconsultancy.com/free/ray_tracer/languages.html) but the performance was not very good (the OCaml version I based it on was at least 10x faster). I would be happy to contribute my code to the benchmark suite if you are interested. Perhaps someone can point out obvious speed-ups that I missed while trying to improve the performance. I would think that what we'd want to benchmark would be clean, optimized actually-used code. I.e. things like Data.Bytestring, so that we could see how compilers differed on important code, or how the code generated on different architectures differed. e.g. if jhc beats ghc on amd64, the ghc developers would probably be very curious as to why, and how to fix it. Code that's not been properly optimized with respect to strictness, etc, would fail to focus the tests on important optimizations of the compiler. But of course, the benchmark code should also be clean, since we want to ensure that our compilers are good enough that we can write useful beautiful code that is also fast. I tried to optimize it, but I couldn't approach the speed of the OCaml version. I followed the performance tuning advice from the Wiki, and had even resorted to writing the inner loop calculations using all unboxed doubles, but without significant improvements. This is exactly the kind of code that I write most often, and I would love to see improvements in the optimizations for this kind of numerically intensive code (especially without having to resort to compiler-specific unboxed representations). I agree that common libraries like ByteString need to be well represented, but the original request additionally included programs that are representative of applications. A ray-tracer (even with a fixed scene and only one type of scene primitive) is a fairly nice approximation of a real numerical batch-oriented application while still being small enough to understand and modify. I expect thats why John chose it as his benchmark application in the first place. I think it would also be a good idea to include SPJ's web server (I think its from an STM paper). A lot of the people outside the Haskell community will be able to relate better to metrics like pages/second. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: A function for Maybes
John Ky wrote: Is there a built-in function that already does this? Usually, when I have a question like this, I try Hoogle first: http://www.haskell.org/hoogle/?q=%28a+-%3E+b%29+-%3E+Maybe+a+-%3E+Maybe+b Unfortunatly, the right answer (fmap) is on the second page of results. (I am really excited for the new version of Hoogle, its supposed to be pretty close to release) foo :: (a - b) - Maybe a - Maybe b foo f m | isNothing m = Nothing | otherwise = Just (f (fromJust m)) *Main foo (+2) (Just 3) Just 5 *Main foo (+2) Nothing Nothing Prelude fmap (+2) (Just 2) Just 4 Prelude fmap (+2) Nothing Nothing it works over all Functors, so list also works: Prelude fmap (+2) [2,3] [4,5] Prelude fmap (+2) [] [] and Map and so on. -- Alan Falloon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
