Proposal for generalized function partition in List-library
Hi all, knowing that the Haskell library report is currently being rewritten, I would like to propose a new function for module List that generalizes the current function partition :: (a -> Bool) -> [a] -> [[a]] in the following way: partition :: Eq b => (a -> b) -> [a] -> [[a]] partition _ [] = [] partition f (a:as) = let (as',as'') = foldr (select (f a)) ([],[]) as in (a:as'):partition f as'' where select b x (ts,fs) | f x == b = (x:ts,fs) | otherwise = (ts,x:fs) This partitioning function builds equivalence classes from the list argument, where each element list within the result list consists of elements that all map to the same value when applying f to it. Thus: partition (`div` 2) [1..5] yields [[1],[2,3],[4,5]] This is much more general than the existing partitioning function and applicable in many practical cases. Cheers, Bernd Holzmüller
On Thu, 17 May 2001, Bernd [iso-8859-2] Holzm�ller wrote:
This partitioning function builds equivalence classes from the list argument, where each element list within the result list consists of elements that all map to the same value when applying f to it. Thus: partition (`div` 2) [1..5] yields [[1],[2,3],[4,5]]
This is much more general than the existing partitioning function and applicable in many practical cases.
But here generality comes at the expense of speed I think. Greetings :-) Michal Gajda korek@icm.edu.pl
this is just how I understand things at the moment, if I am wrong or misleading anywhere then please speak up. I am unconvinced that such generalizations must come as speed hits, but perhaps someone can enlighten me. compilers seem to support seperate compilation and polymorphism at the moment by boxing polymorphic types and passing their class-context (term?) as a hidden parameter to the polymorphic function. but it seems that since haskell is strongly type checked at compile time, we already KNOW all of the types with certainty when it comes to compiling the program in the end so this would seem to be unnecisarry. now there are two cases where this breaks down * seperate compilation * code bloat namely that you don't necisarilly know all of the types of polymorphic functions when they are in a module that is compiled seperately from the rest of the program. the solution used by many C++ compilers is to inline all polymorphic code in place (this is why templates are in header files). there is no reason this won't work in haskell and give back all of the speed benefits of base types everwhere (as it would in this example) but has the unfortunate side effect of causing worst case exponential code bloat as every function is re-written for every type combination it is used with. the solution I see (and probably exists) is a hybrid model, one that lets the compiler know to specialize certain polymorphic functions as well as let the compiler utilize such specialized functions. a pragma which lets the compiler know that a certain specialization would be useful such as partition :: (Eq b) => (a -> b) -> [a] -> [[a]] partition fn ls = ... {-# specialize partition :: (a -> Bool) -> [a] [[a]] -} which would let the compiler know to generate code for partition specificially optimized for (a -> Bool) and thus obviating the need for the Eq hidden argument. the fully polymorphic version would of course also have to be generated. specializations would be advertised in the header file and utilized whenever the typechecker determined you were using partition in the specialized case. this seems like a better solution than the current practice of providing seperate general and specific functions, take, genTake, max, genMax and whatnot. you would just specify that specializations for the case of 'Int' should be generated as it would be the most common case. an {-# inline partition -} might also be useful which would actually place the text of the function into the .hi file to be in-line expanded as is done in C++... I imagine there would be some tweaking to determine when this is a win and when it isn't... some of this stuff probably exists in current compilers, but polymorphism need not be at the expense of speed. -John On Thu, May 17, 2001 at 12:36:39PM +0200, Michal Gajda wrote:
On Thu, 17 May 2001, Bernd [iso-8859-2] Holzmüller wrote:
This partitioning function builds equivalence classes from the list argument, where each element list within the result list consists of elements that all map to the same value when applying f to it. Thus: partition (`div` 2) [1..5] yields [[1],[2,3],[4,5]]
This is much more general than the existing partitioning function and applicable in many practical cases.
But here generality comes at the expense of speed I think.
-- -------------------------------------------------------------- John Meacham http://www.ugcs.caltech.edu/~john/ California Institute of Technology, Alum. john@repetae.net --------------------------------------------------------------
John, On Thu, 17 May 2001, John Meacham wrote: [..]
namely that you don't necisarilly know all of the types of polymorphic functions when they are in a module that is compiled seperately from the rest of the program. the solution used by many C++ compilers is to inline all polymorphic code in place (this is why templates are in header files). there is no reason this won't work in haskell and give back all of the speed benefits of base types everwhere (as it would in this example) but has the unfortunate side effect of causing worst case exponential code bloat as every function is re-written for every type combination it is used with.
This is true in ML but not in Haskell. Haskell has polymorphic recursion which makes it impossible to predict statically at what types a function will be called. So trying to inline away polymorphism would lead to infinite unwindings. Cheers, /Josef
Josef Svenningsson wrote:
John,
On Thu, 17 May 2001, John Meacham wrote:
[..]
namely that you don't necisarilly know all of the types of polymorphic functions when they are in a module that is compiled seperately from the rest of the program. the solution used by many C++ compilers is to inline all polymorphic code in place (this is why templates are in header files). there is no reason this won't work in haskell and give back all of the speed benefits of base types everwhere (as it would in this example) but has the unfortunate side effect of causing worst case exponential code bloat as every function is re-written for every type combination it is used with.
This is true in ML but not in Haskell. Haskell has polymorphic recursion which makes it impossible to predict statically at what types a function will be called. So trying to inline away polymorphism would lead to infinite unwindings.
This is true in theory, but in practice most polymorphism can be removed by inlining. I'm sure some pragmatic solution with limited inlining would work quite well. You'd still need to be able to handle polymorphism without inlining, of course, so you could cope with the exceptional cases. Mark Jones did some experiments with this kind of inlining that worked very well. -- Lennart
Maestri, Primaballerine, I have a really provocative question. One of my student posed it, and I could not respond in a satisfactory manner, especially for myself it was really unsatisfactory. We know that a good part of "top-down" polymorphism (don't ask me what do I mean by that...) in C++ is emulated using templates. Always when somebody mentions templates in presence of a True Functionalist Sectarian, the reaction is "What!? Abomination!!". Now the question: WHY? Why so many people say "the C++ templates are *wrong*" (and at the same time so many people use it every day...) Is it absolutely senseless to make a functional language with templates? Or it is just out of fashion, and difficult to implement? == This is a sequel to a former discussion about macros, of course... Jerzy Karczmarczuk Caen, France
(This response comes from the context of someone who like FP but has a day job writing in C++.) On Fri, 18 May 2001, Jerzy Karczmarczuk wrote:
We know that a good part of "top-down" polymorphism (don't ask me what do I mean by that...) in C++ is emulated using templates.
Umm... what do you mean by `top down'? The two senses in which I use polymorphism in C++ are: (i) using super classes (in the sence that A is a superclass of B is B inherits from A) to perform operations that only make sense for objects of the semantic type A. My canonical example is working with quadtree nodes, where a there are various types nodes which can hold different kinds of data but the base class qnode holds things like position, etc. (ii) using templates to write generic algorithms which either don't depend on the object type at all (e.g., vectors, lists, etc) or which depend on one or two conceptual operations which are very elementary (e.g., meaningful equality, addition or a `display yourself on stdout' function). In C++ these could _almost_ be done using superclasses but with problems because (A) the standard types (e.g., int) can't have their place in the class hierarchy redefined (e.g., int inherits from debug_show) (B) deep hierarchies are really not handled well by debuggers and it'd be a real pain trying to look at the C++ equivalent of the haskell `data A = ... deriving (Show,Ord,Monad,...)' The almost that I referred to above comes from the fact that (AFAIK) without using something nasty like RTTI you can't create new objects of the true type in a function to which you've passed a pointer to the base class. That's the conceptual overview. In terms of pragmatics __at least for my work in image processing__ I don't write classes that much, seldom use inheritance and I'm 99% sure I don't have any inheritance more than 1 level deep. On the other hand I write a lot of templated code which would be equivalent in haskell to either f :: a -> b -> .... -> a or f :: Eq a => a -> b -> ... -> a (i.e., algorithms that need just one or two low-level ideas such as equality). I much prefer the Haskell way of doing this with superclasses but I just don't feel brave enough to attempt the levels of class hierarchy that this implies in C++. (In some ways this is a shame since, because in template function names member functions used are only matched syntactically -- as there's no superclass to ensure semantic equivalence -- I've made one or two mistakes when I forgot a member function with the same name actually meant something different.)
Always when somebody mentions templates in presence of a True Functionalist Sectarian, the reaction is "What!? Abomination!!".
Now the question: WHY?
Why so many people say "the C++ templates are *wrong*" (and at the same time so many people use it every day...)
In my experience the C++ idiom `you only pay for what you use' (==> templates are essentially type-checked macros) and the fact most compilers are evolved from C compilers makes working with templates a real pain in practice. Additionally, I think a lot of people who dislike them are old-time C hackers who don't see why it isn't good enough to do polymorphism via void*'s and function pointers. As to why I at least use it, it lets me write polymorphic functions without needing deep class hierarchies (which as noted above aren't nice in C++) or going into the error prone mire of the void* approach.
Is it absolutely senseless to make a functional language with templates? Or it is just out of fashion, and difficult to implement?
I may be missing something obvious, but given Haskell's well thought out (IMO) prelude class structure and the fact that deep class hierarchies with `multiple inheritance' aren't a problem in Haskell, I don't see that it would buy you anything in Haskell. On the other hand, if the standard prelude didn't have the class hierarchy I think they would be much more useful. ___cheers,_dave________________________________________________________ www.cs.bris.ac.uk/~tweed/pi.htm|tweed's law: however many computers email: tweed@cs.bris.ac.uk | you have, half your time is spent work tel: (0117) 954-5250 | waiting for compilations to finish.
On Fri, 18 May 2001, Jerzy Karczmarczuk wrote:
We know that a good part of "top-down" polymorphism (don't ask me what do I mean by that...) in C++ is emulated using templates.
Always when somebody mentions templates in presence of a True Functionalist Sectarian, the reaction is "What!? Abomination!!".
Now the question: WHY?
ordinary FP polymorphish is as strict analogue of the C++ template-functions Haskell type clasess is as close analog for the C++ template classes (studing of the Haskell type classes clarify to me many aspects of the C++ classes templates semantic). Regards, Anton
Fri, 18 May 2001 11:25:14 +0200, Jerzy Karczmarczuk <karczma@info.unicaen.fr> pisze:
Always when somebody mentions templates in presence of a True Functionalist Sectarian, the reaction is "What!? Abomination!!".
They aren't that wrong, but they have some problems: * It's not specified what interface they require from types to be instantiated to. * The whole implementation must be present in a public header file. Well, there is the 'export' keyword, but no compiler implements it. It follows that all things used by implementation of a template must be included too. And compilation time of a large project is larger than necessary. * They introduce very complex rules about name lookup (environment in which a specialized template is compiled is a weird mix of environments of the point of definition and point of usage of the template), deduction which overloading to use (with choosing the candidate according to partial ordering of better fitting), deduction of template types and what partial specialization to use, complicated by the fact that there are complex rules of implicit conversions. Templates don't obey a Haskell's rule that adding code doesn't change the meaning of previously valid code and can at most introduce an ambiguity which is flagged as error. * Types can't be deduced from the context of usage. For example handling the empty set or monadic 'return' would require either spelling the type at each use or introducing another type and deferring deduction of the real type until an operation is performed with a value of a known type. * Since they are similar to macros, they tend to give horrible error messages which mentions things after expansion. Here is what I once got: mico-c++ -Wall -I. -c serwer.cc -o serwer.o serwer.cc: In method `void Firma_impl::usun(const char *)': serwer.cc:92: `struct __rb_tree_iterator<pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *>,const pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> &,const pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> *>' has no member named `second' serwer.cc:93: no matching function for call to `map<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *,less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >,__default_alloc_template<true,0> >::erase (__rb_tree_iterator<pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *>,const pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> &,const pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> *> &)' /usr/include/g++/stl_map.h:156: candidates are: map<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *,less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >,__default_alloc_template<true,0> >::erase<string, Katalog *, less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >, alloc>(__rb_tree_iterator<pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *>,pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> &,pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> *>) /usr/include/g++/stl_map.h:157: map<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *,less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >,__default_alloc_template<true,0> >::erase<string, Katalog *, less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >, alloc>(const string &) /usr/include/g++/stl_map.h:158: map<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *,less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >,__default_alloc_template<true,0> >::erase<string, Katalog *, less<basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> > >, alloc>(__rb_tree_iterator<pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *>,pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> &,pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> *>, __rb_tree_iterator<pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *>,pair<const basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >,Katalog *> &,pair<const basic_string<char,string_char_traits<char>, __default_alloc_template<true,0> >,Katalog *> *>) make: *** [serwer.o] Error 1 They also have some advantages over mechanisms available in Haskell: * A templatized class can contain types, values with arbitrary types, other templates etc. so it's easy to have parametrization of all things by types. Haskell requires fundeps, dummy arguments and local quantifiers to handle these things - sometimes it's not nice. * A template can be parametrized by values of primitive types (by expressions using builtin operations which can be evaluated at compile time). Yes, it's ugly that types and operations don't have equal rights, but it's sometimes useful. * A template is in practice guaranteed to be specialized to used types, so they don't have a performance overheads over non-templatized variants. My not-quite-done-right attempt at inlining dictionary functions in ghc is a step in this direction, as is the proposal of export-unfolding-and-specialize-but-not-necessarily-inline. I hope that SimonPJ will sort this out. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
Lennart wrote:
This is true in theory, but in practice most polymorphism can be removed by inlining. I'm sure some pragmatic solution with limited inlining would work quite well. You'd still need to be able to handle polymorphism without inlining, of course, so you could cope with the exceptional cases.
Mark Jones did some experiments with this kind of inlining that worked very well.
-- Lennart
The MLton compiler (http://www.clairv.com/MLton/) uses whole program compilation and monomorphises ML code (again they do not have to deal with potential polymorhpic recursion, but as Lennart says, it can be treated as a special case in Haskell). I have never used it though, so I can't vouch for its performance. They are motivated to use unboxed representations and so on. The danger with whole program compilation is long compile times. But it might be possible to allow separate compilation for development and put up with the overheads of boxed representations and so on, but get the benefits of the optimisations flowing from whole program compilation when needed (ie released binaries). Sounds like a lot of work to me though. Bernie.
this is interesting, could someone give an example of how polymorphic recursion would disallow specialization of a function? i mean, it seems to me that even if you had recursion, you still have to actually call the function at some point with some real type and at that point you can decide whether to use the specialized version or not. One of the main things i was hopeing was that the seperate 'generic' and 'concrete' functions in the Prelude could be dumped for just the generic ones. the compiler should be able to optimize for the common cases of Nums being Ints and whatnot. (with the help of some pragma annotations.) -John On Fri, May 18, 2001 at 10:32:54AM +0200, Josef Svenningsson wrote:
John,
On Thu, 17 May 2001, John Meacham wrote:
[..]
namely that you don't necisarilly know all of the types of polymorphic functions when they are in a module that is compiled seperately from the rest of the program. the solution used by many C++ compilers is to inline all polymorphic code in place (this is why templates are in header files). there is no reason this won't work in haskell and give back all of the speed benefits of base types everwhere (as it would in this example) but has the unfortunate side effect of causing worst case exponential code bloat as every function is re-written for every type combination it is used with.
This is true in ML but not in Haskell. Haskell has polymorphic recursion which makes it impossible to predict statically at what types a function will be called. So trying to inline away polymorphism would lead to infinite unwindings.
Cheers, /Josef
-- -------------------------------------------------------------- John Meacham http://www.ugcs.caltech.edu/~john/ California Institute of Technology, Alum. john@repetae.net --------------------------------------------------------------
Fri, 18 May 2001 12:32:11 -0700, John Meacham <john@repetae.net> pisze:
this is interesting, could someone give an example of how polymorphic recursion would disallow specialization of a function?
test:: Show a => a -> [String] test x = show x : test [x] -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
From: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>
Fri, 18 May 2001 12:32:11 -0700, John Meacham <john@repetae.net> pisze:
this is interesting, could someone give an example of how polymorphic recursion would disallow specialization of a function?
test:: Show a => a -> [String] test x = show x : test [x]
Another source of programs needing polymorphic recursion are non-regular datatypes, which occur frequently in Chris Okasaki's _Purely_Functional_Data_Structures_. A bare-bones example is: | data Perfect a = One a | Two (Perfect (a,a)) | deriving Show | | mkPerfect :: Int -> a -> Perfect a | mkPerfect 1 x = One x | mkPerfect (n+1) x = Two (mkPerfect n (x,x)) mkPerfect will be called with a number of different types for its second argument, depending on the first argument. HTH, Jan de Wit
Thu, 17 May 2001 10:06:55 +0200, Bernd Holzmüller <holzmueller@ics-ag.de> pisze:
I would like to propose a new function for module List that generalizes the current function partition :: (a -> Bool) -> [a] -> [[a]]
No, current partition has type (a -> Bool) -> [a] -> ([a], [a]) so your function is not compatible with it, so shouldn't replace such standard function.
partition:: Eq b => (a -> b) -> [a] -> [[a]] partition _ [] = [] partition f (a:as) = let (as',as'') = foldr (select (f a)) ([],[]) as in (a:as'):partition f as'' where select b x (ts,fs) | f x == b = (x:ts,fs) | otherwise = (ts,x:fs)
This function doesn't give a hint which sublists correspond to which results of the function, so I'm afraid it's easy to make errors by assuming that they will come in a different order. And it's inefficient: the cost is the number of elements times the number of different results of the function. I would write it thus: \f xs -> groupBy (\(a, _) (b, _) -> a == b) $ sortBy (\(a, _) (b, _) -> compare a b) [(f x, x) | x <- xs] You can apply 'map (map snd)' to the result to remove the results of f. I don't have a good name for it and I'm not sure it's common enough to put it in the standard library. It can also be more efficiently written using Array.accumArray for particular types of the result of the function. PS. What I would perhaps put into standard library: uniq :: Eq a => [a] -> [a] uniqBy :: (a -> a -> Bool) -> [a] -> [a] so people don't use nub unnecessarily (if elements are adjacent or can be made adjacent by sorting), and takeLastWhile :: (a -> Bool) -> [a] -> [a] dropLastWhile :: (a -> Bool) -> [a] -> [a] spanEnd :: (a -> Bool) -> [a] -> ([a], [a]) (with some better names) which iterate forward and are lazy, to avoid double reversing in case the test is cheap but the list is long, and partitionM :: Monad m => (a -> m Bool) -> [a] -> m ([a], [a]) Here are implementations of some of these: takeLastWhile p xs = case span p xs of (ys, []) -> ys (_, _:zs) -> takeLastWhile p zs dropLastWhile p xs = case span p xs of (_, []) -> [] (ys, z:zs) -> ys ++ z : dropLastWhile p zs spanEnd p xs = case span p xs of (ys, []) -> ([], ys) (ys, z:zs) -> (ys ++ z : ys', zs') where (ys', zs') = spanEnd p zs -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
17 May 2001 19:36:44 GMT, Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> pisze:
PS. What I would perhaps put into standard library:
And also: split :: (a -> Bool) -> [a] -> [[a]] split p c = let (xs, ys) = break p c in xs : case ys of [] -> [] _:zs -> split p zs softSplit :: (a -> Bool) -> [a] -> [[a]] -- softSplit p c = filter (not . null) (split p c) softSplit p c = case dropWhile p c of [] -> [] x:xs -> let (ys, zs) = break p xs in (x:ys) : softSplit p zs It follows that words = softSplit isSpace. Any better name? -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
participants (11)
-
Anton Moscal -
Bernard James POPE -
Bernd Holzmüller -
D. Tweed -
Jan de Wit -
Jerzy Karczmarczuk -
John Meacham -
Josef Svenningsson -
Lennart Augustsson -
Marcin 'Qrczak' Kowalczyk -
Michal Gajda