Thanks for the comments. It seems the function is not really needed (at least not predefined), although I use it fairly often.
Read more in
T Uustalu, V Vene. The dual of substitution is redecoration. In K Hammond, S Curtis, eds, Trends in Functional Programming 3, pp 99-110. Intellect, Bristol / Portland, OR, 2002. - .ps.gz, 46K (© Intellect)
http://www.cs.ioc.ee/~tarmo/papers/sfp01-book.ps.gz ,
if you want to be bothered with categorical nonsence ;-)
There's too much mathematics in it, I'm only an engineer... ;-) Thanks, Markus -- Markus Schnell, Infineon Technologies AG
Hi Markus -- Your comment: Markus.Schnell@infineon.com wrote:
There's too much mathematics in it, I'm only an engineer... ;-)
reminds of what I think is one of the biggest problems with conventional software development: the lack of appreciable mathematics in the specification, design, coding, or implementation of programs. In this sense there is a huge contrast between conventional software development practice and other engineering disciplines. I was once an electrical engineer, and I used lots of mathematics (not just in school, but in industry), and I know that most other engineering disciplines also use a lot of mathematics. One of the things I like about FP is that it demands more mathematical sophistication of its practitioners, which, contrary to some opinions, I think is a Good Thing. So, I know that you had a smiley after your comment, but I encourage you to take opportunities like this to learn a little more mathematics if you can! (I know I do...) Best regards, -Paul
G'day all. On Thu, Nov 28, 2002 at 12:32:19PM -0500, Paul Hudak wrote:
reminds of what I think is one of the biggest problems with conventional software development: the lack of appreciable mathematics in the specification, design, coding, or implementation of programs.
In the interest of fairness, the declarative programming community occasionally appears to have an aversion to actual engineering. If you mention a term like "design patterns", people look down their virtual noses at you like you're trying to infect their pure theoretical world with something unsanitary. My point is that nobody is immune from this kind of thinking, it just takes different forms. Cheers, Andrew Bromage
On Mon, 2 Dec 2002, Andrew J Bromage wrote:
... If you mention a term like "design patterns",
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc. I think you need `design pattern' as a special concept only if you can't express it in the language itself (that is, if all your functions are first order, if you can't write polymorphic code, or can't typecheck it properly, etc.) as it happens for most of the mainstream languages ... -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/207 --
On Mon, 2 Dec 2002, Andrew J Bromage wrote:
... If you mention a term like "design patterns",
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc.
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
Or maybe more general notions, such as "define a recursive datatype together with a catamorphism combinator" or even "embed a domain-specific language via combinators over an ADT" There are patterns of that sort in our programs, which we would probably rather call design techniques, which aren't so easily captured by a higher-order function definition. John
John Hughes wrote (on 02-12-02 10:27 +0100):
On Mon, 2 Dec 2002, Andrew J Bromage wrote:
... If you mention a term like "design patterns",
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc.
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
Or maybe more general notions, such as
"define a recursive datatype together with a catamorphism combinator"
or even
"embed a domain-specific language via combinators over an ADT"
There are patterns of that sort in our programs, which we would probably rather call design techniques, which aren't so easily captured by a higher-order function definition.
And yet these are two examples which might reasonably be adopted, like HOFs, as language features: 1) most recursive datatypes, including nested datatypes, determine a unique catamorphism, so we could generate it for the user automatically, or provide a fold-expression analagous to the case-expression, as in Charity; 2) similarly, many polymorphic datatypes, together with a specification of a notion of variable or environment, determine a substitution monad for an embedded DSL, so we could generate the map, unit, join, bind and substitution functions automatically from the spec, and I imagine one could provide a sort of quasiquotation syntax for specifying terms of the DSL (which is, though, not so far from do-syntax as we have it now). There is a strong trend in declarative languages, I think, where "design patterns" evolve into more bullet-proof language features, precisely because design techniques in declarative languages are susceptible to formal analysis. For example, I think this is how algebraic datatype declarations (and perhaps arguably modules) evolved in ML. In a short discussion at the end of Tatsuya Hagino's thesis ("A Categorical Programming Language"), he describes how abstract datatypes were adopted by SML as a primitive part of the declaration syntax. In the original ML developed for LCF, datatypes were declared like this: absrectype btree = int + (btree # btree) with leaf n = absbtree(inl n) and node(t1,t2) = absbtree(inr(t1,t2)) and isleaf t = isl(repbtree t) and leafvalue t = outl(repbtree t) and left t = fst(outr(repbtree t)) and right t = snd(outr(repbtree t));; The modern equivalent is: data Btree = Leaf Int | Node (Btree, Btree) Imagine (or, "recall", if you are old enough :) having to declare all those introduction and elimination primitives for every datatype! Maybe in a few years we will be looking back and saying the same about catamorphisms and DSLs... -- Frank
John Hughes wrote:
On Mon, 2 Dec 2002, Andrew J Bromage wrote:
... If you mention a term like "design patterns",
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc.
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
Or maybe more general notions, such as
"define a recursive datatype together with a catamorphism combinator"
or even
"embed a domain-specific language via combinators over an ADT"
There are patterns of that sort in our programs, which we would probably rather call design techniques, which aren't so easily captured by a higher-order function definition.
It seems like all the patterns, at least the ones in the GoF's enumeration, can be expressed as higher-order functions and classes if we only would have a way to traverse a record structure dynamically. If someone can think of a "design pattern" (such as one from the GoF book) which is not expressible directly in Haskell, up to data type structure (i.e., assuming the structure to be list or a fixed tree structure...), please let us know. Till then, we "Haskellers" will probably continue expressing our patterns either directly in Haskell or using highly formal language, with terms such as "catamorphisms". The virtue, and weakness, of traditional design patterns is their vagueness and informal character, making them (1) comprehensible to the 90% of the developer community not familiar with category theory but (2) constituting only vague schemes for implementation; in fact, they are often so vague that it takes quite some effort to determine whether a fragment of code follows a pattern. Actually, showing a fragment of code to a group of software enginers and having them pick the pattern embodied will probably lead to differing opinions. In Haskell-land, or in any other land on the Functional continent, a catamorphism is a catamorphism: as soon as an engineer recognizes the algorithm of a code fragment, he will immediately determine the catamorphic (or any other <X>morhpic) character. No fuss, no differing opinions. Ah, this is my land... /David
On Mon, 2 Dec 2002 13:05:27 -0500 "David Bergman" <davidb@home.se> wrote:
or using highly formal language, with terms such as "catamorphisms".
Ok I can't resist longer. It's ages I have been wondering what's a catamorphism, and an anamorphism, and what the hell does it mean "data is expressed by destructors and not by constructors", but I have had no time till now. Please some of you all catamorphism experts tell me a good and clear article to read :))) Vincenzo -- Teatri vuoti e inutili potrebbero affollarsi se tu ti proponessi di recitare te [CCCP] Il contenuto di questa e-mail può essere modificato e redistribuito purchè questa nota e il suo significato rimangano intatti.
Nick Name writes: : | Ok I can't resist longer. It's ages I have been wondering what's a | catamorphism, and an anamorphism, and what the hell does it mean | "data is expressed by destructors and not by constructors", but I | have had no time till now. Please some of you all catamorphism | experts tell me a good and clear article to read :))) As a reader but not an expert, I recommend http://www.cse.ogi.edu/~mpj/pubs/springschool.html
--- Tom Pledger <Tom.Pledger@peace.com> wrote:
Nick Name writes: : | Ok I can't resist longer. It's ages I have been wondering what's a | catamorphism, and an anamorphism, and what the hell does it mean | "data is expressed by destructors and not by constructors", but I | have had no time till now. Please some of you all catamorphism | experts tell me a good and clear article to read :)))
As a reader but not an expert, I recommend http://www.cse.ogi.edu/~mpj/pubs/springschool.html
There's also Lex Augusteijn "Sorting Morphisms" (1998) http://citeseer.nj.nec.com/augusteijn98sorting.html http://www.di.uminho.pt/afp98/PAPERS/Lex.ps A useful paper on the various -morphisms in the famous Bananas series of titles: Erik Meijer, Graham Hutton Bananas in Space: Extending Fold and Unfold to Exponential Types (1995) http://citeseer.nj.nec.com/meijer95bananas.html http://www.cs.nott.ac.uk/~gmh/bananas.ps The more abstract, original Bananas paper: Erik Meijer, Maarten Fokkinga, Ross Paterson Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991) http://citeseer.nj.nec.com/meijer91functional.html http://research.microsoft.com/~emeijer/Papers/fpca91.pdf http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.ps There are other Bananas out there, but some have to do with imports and tariffs... ;-) Chris ===== Christopher Milton cmiltonperl@yahoo.com __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com
As a reader but not an expert, I recommend http://www.cse.ogi.edu/~mpj/pubs/springschool.html
It seems also a good summary of everything haskell-related :) Thanks, it is useful to me. Vincenzo
G'day all. On Mon, Dec 02, 2002 at 01:05:27PM -0500, David Bergman wrote:
It seems like all the patterns, at least the ones in the GoF's enumeration, can be expressed as higher-order functions and classes if we only would have a way to traverse a record structure dynamically. If someone can think of a "design pattern" (such as one from the GoF book) which is not expressible directly in Haskell, up to data type structure (i.e., assuming the structure to be list or a fixed tree structure...), please let us know.
Here's one: Gérard P. Huet, "The Zipper." JFP 7(5): 549-554 (1997) This pattern, used for traversing data structures in all directions including "up", is directly expressible in languages with pointers but is not directly expressible in Haskell 98 (unless you use indirect data structures, but they remove a lot of the benefit of using Haskell ata structures, like pattern matching) so the zipper pattern (or something like it) is required. No, I didn't pick an example from the GoF book. The GoF book deals exclusively with imperative OO languages, so we should not expect their particular set of patterns to be as useful to us. Cheers, Andrew Bromage
G'day all. On Mon, Dec 02, 2002 at 10:27:21AM +0100, John Hughes wrote:
There are patterns of that sort in our programs, which we would probably rather call design techniques, which aren't so easily captured by a higher-order function definition.
As a matter of interest, _why_ would we rather call them "design techniques" than "design patterns"? Is it just an aversion to buzzwords, or are they fundamentally different? Cheers, Andrew Bromage
On Tue, 3 Dec 2002, Andrew J Bromage wrote:
On Mon, Dec 02, 2002 at 10:27:21AM +0100, John Hughes wrote:
There are patterns of that sort in our programs, which we would probably rather call design techniques, which aren't so easily captured by a higher-order function definition.
As a matter of interest, _why_ would we rather call them "design techniques" than "design patterns"? Is it just an aversion to buzzwords, or are they fundamentally different?
No particular reason, maybe, except that the buzzword isn't established in our community. And no wonder, since we have no catalogue of Haskell "design patterns" -- we're not even completely sure what they are! If there were such a catalogue, and it became popular among Haskell users, and it called the entries design patterns, then that would establish the term. One difference which I see between a "technique" and a "pattern" is that there is a uniform and somewhat formal way of describing patterns: thought has been put into what you should document when you describe a pattern. Maybe we should stick to vaguer terms such as "technique" until we've put in the corresponding thought! John
G'day all. On Mon, Dec 02, 2002 at 08:26:06AM +0100, Johannes Waldmann wrote:
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc.
Can I safely translate that as "We use design patterns but we don't like the name?" In a different language, you use different design patterns. Just as iterator-based patterns are next to useless in Haskell (where we have lazy streams), patterns based on CPS are next to useless in a language with state and non-local return constructions. Cheers, Andrew Bromage
Andrew J Bromage wrote (on 03-12-02 09:52 +1100):
On Mon, Dec 02, 2002 at 08:26:06AM +0100, Johannes Waldmann wrote:
well I love design patterns, it's just that in Haskell-land they are called higher-order functions, or polymorphic functions, etc.
Can I safely translate that as "We use design patterns but we don't like the name?"
In a different language, you use different design patterns. Just as iterator-based patterns are next to useless in Haskell (where we have lazy streams), patterns based on CPS are next to useless in a language with state and non-local return constructions.
I think there is a world of difference between GoF-style design patterns and things like HOFs, polymorphism and whatnot in Haskell. If you are programming GUI applications in C and use callbacks for the widget actions, then you are basically using the design pattern which gets formalized as HOFs in an ML-like language. But C will not guarantee for you that you callback function is well-typed, hold onto the data in the closure, do the necessary garbage collection, etc. Those things may seem like details, but they are what make HOFs robust and practical to use ubiquitously; the callback design pattern, since it is basically puts the burden on the programmer, can never hope to achieve that degree of robustness. Furthermore, design patterns come with a set of informal hints about when and where to apply the pattern. The notion of HOF is, of course, completely neutral about this, except insofar as the type system forces you to provide a HOF where a function is expected. OTOH, the advice that "you should use HOFs to model widget actions" or "you should use HOFs to allow customization of applications via hooks" (as in Emacs LISP) could reasonably be construed as a design pattern. So maybe a design pattern can be regarded as a correspondence between formal concepts and domain-specific ones. -- Frank
[Frank Atanassow <franka@cs.uu.nl>]
Furthermore, design patterns come with a set of informal hints about when and where to apply the pattern. The notion of HOF is, of course, completely neutral about this, except insofar as the type system forces you to provide a HOF where a function is expected. OTOH, the advice that "you should use HOFs to model widget actions" or "you should use HOFs to allow customization of applications via hooks" (as in Emacs LISP) could reasonably be construed as a design pattern. So maybe a design pattern can be regarded as a correspondence between formal concepts and domain-specific ones.
i think this (especially the last sentence) is a crucial observation. all too often, the fp community (communities) seems to write design patterns off on the grounds that "our languages do that stuff for us". this is based on far too unsophisticated an understanding of design patterns. certainly the patterns that are useful in c++ will not all be useful in haskell, and many of them will even appear trivial. but this does not mean that the appropriate correspondence(s) "between formal concepts and domain-specific ones" will always be obvious. in fact, this is exactly the kind of information that programmers new to haskell need more of. one of the purposes of design patterns is to capture the idiom of a particular language, often using fairly specific domain examples. "to solve this kind of problem in this language, these are the usual techniques. here are guidelines for choosing between them..." these guidelines often include, for example, which techniques work well (or poorly) with which others, some counter-indications for using a particular technique, which techniques excel in particular circmstances ("pattern A is a better choice when you expect to register callbacks only once and use them many times, while B is a better choice when you expect callbacks to change quite frequently"), etc. i hope it's obvious that this is significantly more information, and significantly more useful, than: "when you need something like callbacks, use hofs." i know i'm not the only programmer who understands most of the syntax and semantics of haskell, but still feels far less than confident engineering a program of any decent size. while there's really no substitute for experience, i really believe we could benefit from some patterns. m -- matt hellige matt@immute.net http://matt.immute.net
size. while there's really no substitute for experience, i really believe we could benefit from some patterns.
There was a list of design patterns for Haskell on the Wiki (back in the days when it worked): http://haskell.org/wiki/wiki?CommonHaskellIdioms --KW 8-) -- Keith Wansbrough <kw217@cl.cam.ac.uk> http://www.cl.cam.ac.uk/users/kw217/ University of Cambridge Computer Laboratory.
I shamelessly copy from the abstract of [1]: We contend that design patterns can be an effective means of consolidating and communicating program construction expertise for functional programming just as they have proven to be in object-oriented programming. One might suppose that the powerful abstraction mechanisms of functional programming obviate the need for design patterns, since many pieces of program construction knowledge can be captured by reusable functions. This confusion of design patterns with reusable components misses the point: patterns start where components end, in the sense that the former describe how the latter can be constructed and used. Thus, additional abstraction \emph{creates} the need for new design patterns. [1] Design Patterns for Functional Strategic Programming http://www.cs.vu.nl/Strafunski/dp-sf/ Ralf P.S.: Should we move to haskell-cafe@... ? -- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
On Mon, Dec 02, 2002 at 10:37:09AM +1100, Andrew J Bromage wrote:
In the interest of fairness, the declarative programming community occasionally appears to have an aversion to actual engineering. If you mention a term like "design patterns", people look down their virtual noses at you like you're trying to infect their pure theoretical world with something unsanitary. My point is that nobody is immune from this kind of thinking, it just takes different forms.
I've got some issues here: (1) Various things I'm doing as a practitioner lack theoretical background (and/or content) for various problems in them. e.g. how does one measure per-cpu time spent waiting on io on SMP? e.g. page replacement mixes kinds of memory, creating list searches (2) In theory and in practice I've seen "design patterns" and a couple other "popular" programming movements add up to nothing. Design patterns in particular produced precisely zero useful code or code design during its entire lifetime as designs on the level on which its principles operate are not ever getting freshly redone. (3) Various tidbits of theoretically motivated languages assume so much infrastructure as to be unsuitable for various (kernel) environments. There's a circular dependency between what some things implement and the infrastructure assumed, which is where the problem lies. (4) There is no excuse for willful ignorance. Linear searches in interrupt context and other gross inefficiencies have brought systems down because the events triggering the poor algorithms occurred in realtime and are generated by hardware. They consistently livelocked boxen with sufficient cpu counts. At any rate, the gist of all this is that even though I don't use much in the way of theory now, I would like to use more of it, and there are various things I wouldn't mind having that aren't universally available. A much lower-level language (i.e. one requiring far less infrastructure) with a decent type system and some modularity would be nice for systems programming, which is the majority of my work, but it really just doesn't make a difference because the work is generally concentrated on a given preexisting system, which isn't going to get converted between languages. And last, but not least, programming is a mathematical discipline. Even the most dreary programming tasks are phraseable as such. (1) hardware does not obey spec, but driver is needed -- augment the driver's state machine to handle new error cases (2) ridiculous code/patch merging constraints are enforced -- analyze program structure to devise incremental merge strategy (3) make process interaction and/or scheduling decision -- scheduling has lots of mathematical stuff behind it None of this is to say that I haven't made extensive and highly beneficial use of Haskell in userspace, which I have. It is a full- blooded substitute for perl, python, and several other "scripting" languages that supposedly ride on the breadth of their libraries that instead remains self-contained without the need for domain-specific library knowledge, which is by all measures a great boon (substituting general for specific knowledge). The highly general, flexible, and expressive language semantics infrastructure negates the need for many preassembled libraries meant to avoid tasks that are generated by the awkwardness of expressing various idioms in less powerful languages. Bill
Hi, Bill. I agree 90% with you in your questioning the adequateness of trying to incorporate design patterns in Haskell, and the actual productive use of them in other languages as well. But, I must defend design patterns, and Haskell, a bit... William Lee Irwin III wrote:
On Mon, Dec 02, 2002 at 10:37:09AM +1100, Andrew J Bromage wrote:
In the interest of fairness, the declarative programming community occasionally appears to have an aversion to actual engineering. If you mention a term like "design patterns", people look down their virtual noses at you like you're trying to infect their pure theoretical world with something unsanitary. My point is that nobody is immune from this kind of thinking, it just takes different forms.
I've got some issues here:
(1) Various things I'm doing as a practitioner lack theoretical background (and/or content) for various problems in them. e.g. how does one measure per-cpu time spent waiting on io on SMP? e.g. page replacement mixes kinds of memory, creating list searches
What has this to do with design patterns? There is, as you know, certainly no need for theoretical substance in order to either define or apply design patterns. They are often quite vague and pragmatic. Oh, I see, you switch between critizising design patterns and declarative languages... Ok, I will try to follow.
(2) In theory and in practice I've seen "design patterns" and a couple other "popular" programming movements add up to nothing. Design patterns in particular produced precisely zero useful code or code design during its entire lifetime as designs on the level on which its principles operate are not ever getting freshly redone.
I have used design patterns mainly as (1) a common language in communication with development teams and (2) as a library of thought patterns (adornments, visitors, wrapper etc.) for less experienced developers (i.e., developers not having built up these patterns "implicitly"). So, the use of design patterns is *not* mainly to create code directly, but rather a common terminology within teams and communities. But, design patterns are clearly overestimated as a tool for (indirect) code production, you are right in that.
(3) Various tidbits of theoretically motivated languages assume so much infrastructure as to be unsuitable for various (kernel) environments. There's a circular dependency between what some things implement and the infrastructure assumed, which is where the problem lies.
What infrastructure are you referring to?
(4) There is no excuse for willful ignorance. Linear searches in interrupt context and other gross inefficiencies have brought systems down because the events triggering the poor algorithms occurred in realtime and are generated by hardware. They consistently livelocked boxen with sufficient cpu counts.
Yes, linear search is certainly bad, not only in that particular context, but in all... We can all agree on that one.
At any rate, the gist of all this is that even though I don't use much in the way of theory now, I would like to use more of it, and there are various things I wouldn't mind having that aren't universally available.
A much lower-level language (i.e. one requiring far less infrastructure) with a decent type system and some modularity would be nice for systems programming, which is the majority of my work, but it really just doesn't make a difference because the work is generally concentrated on a given preexisting system, which isn't going to get converted between languages.
There is one such language: C (if you can call the type system decent...)
And last, but not least, programming is a mathematical discipline. Even the most dreary programming tasks are phraseable as such.
(1) hardware does not obey spec, but driver is needed -- augment the driver's state machine to handle new error cases (2) ridiculous code/patch merging constraints are enforced -- analyze program structure to devise incremental merge strategy (3) make process interaction and/or scheduling decision -- scheduling has lots of mathematical stuff behind it
It is also fruitful to separate "formal" and "mathematical" a bit, since most people tend to diverge into differential geometries, categories, Gilbert spaces etc. when "mathematics" is mentioned, but stay still when "formal" arguments are presented. I.e., your example scenarios above would probably be best classified as formal. Yes, I know that everything formal is mathematical when scrutinized...
None of this is to say that I haven't made extensive and highly beneficial use of Haskell in userspace, which I have. It is a full- blooded substitute for perl, python, and several other "scripting" languages that supposedly ride on
Although I do use Haskell for small (in the complexity sense) systems tasks sometimes, there is a certain pain in my stomach when people classify Haskell as a scripting language. Developing solutions to problems is not always scripting (at least not in my problem fields), and Haskell expressiveness comes to its full right in solving non-trivial (also, complexity-wise) problems.
the breadth of their libraries that instead remains self-contained without the need for domain-specific library knowledge, which is by all measures a great boon (substituting general for specific knowledge). The highly general, flexible, and expressive language semantics infrastructure negates the need for many preassembled libraries meant to avoid tasks that are generated by the awkwardness of expressing various idioms in less powerful languages.
I hope the Perl+Unix+awk+crontab people do not kidnap Haskell. I think there are enough linear approaches to "quick solutions". Let us keep Haskell non-linear! As you said earlier, that would simplify expressing solutions to non-linear problems. That is the tool needed. /David
G'day all. Just to clarify... On Tue, Dec 03, 2002 at 12:42:21PM -0500, David Bergman wrote:
But, design patterns are clearly overestimated as a tool for (indirect) code production, you are right in that.
Absolutely agreed. Design patterns are little more than: - A common language for engineers to talk to each other. - Good documentation. - A useful way to get engineering experience across to a mentoree. Yes, patterns are over-hyped. Nevertheless, there's a baby somewhere in all that bathwater. Cheers, Andrew Bromage
participants (14)
-
Andrew J Bromage -
Christopher Milton -
David Bergman -
Frank Atanassow -
Johannes Waldmann -
John Hughes -
Keith Wansbrough -
Markus.Schnell＠infineon.com -
matt hellige -
Nick Name -
Paul Hudak -
Ralf Laemmel -
Tom Pledger -
William Lee Irwin III