RE: HUGS error: Unresolved overloading
Hi David, | Can anyone shed some light on the following error? Thanks in advance. | | isSorted :: Ord a => [a] -> Bool | isSorted [] = True | isSorted [x] = True | isSorted (x1:x2:xs) | | x1 <= x2 = isSorted (x2:xs) | | otherwise = False I'm branching away from your question, but hope that you might find some additional comments useful ... the last equation in your definition can actually be expressed more succinctly as: isSorted (x1:x2:xs) = (x1 <= x2) && isSorted (x2:xs) This means exactly the same thing, but, in my opinion at least, is much clearer. In fact there's a really nice way to redo the whole definition in one line using standard prelude functions and no explicit recursion: isSorted xs = and (zipWith (<=) xs (tail xs)) In other words: "When is a list xs sorted? If each element in xs is less than or equal to its successor in the list (i.e., the corresponding element in tail xs)." I know this definition may look obscure and overly terse if you're new to either (a) the prelude functions used here or (b) the whole style of programming. But once you get used to it, the shorter definition will actually seem much clearer than the original, focusing on the important parts and avoiding unnecessary clutter. I don't see many emails on this list about "programming style", so this is something of an experiment. If folks on the list find it interesting and useful, perhaps we'll see more. But if everybody else thinks this kind of thing is a waste of space, then I guess this may be the last such posting! All the best, Mark
Hi Mark,
isSorted xs = and (zipWith (<=) xs (tail xs))
In other words: "When is a list xs sorted? If each element in xs is less than or equal to its successor in the list (i.e., the corresponding element in tail xs)."
That's right ... under cbn! At the same time David's version with explicit recursion is fine both in Hugs and in a strict language. I recently started using Caml for day to day work and I get bitten because of the 'lazy mindset' at least once a week. I am not in disagreement with you over the style, but explicit recursion in this case avoids the problem. Cheers, Laszlo PS. Why not go all the way and . uncurry (zipWith (<=)) . id >< tail . dup with appropriate definitions for dup and >< (prod)?
Laszlo Nemeth wrote:
isSorted xs = and (zipWith (<=) xs (tail xs))
In other words: "When is a list xs sorted? If each element in xs is less than or equal to its successor in the list (i.e., the corresponding element in tail xs)."
That's right ... under cbn! At the same time David's version with explicit recursion is fine both in Hugs and in a strict language.
I recently started using Caml for day to day work and I get bitten because of the 'lazy mindset' at least once a week. I am not in disagreement with you over the style, but explicit recursion in this case avoids the problem.
I find this remark very interesting. It reminds me of the many people who say that they want a call-by-value language that allows call-by-need annotations, because you rarely need call-by-need. That depends very much on what you mean by `need call-by-need'! Mark has given a nice example how a function can be defined concisely, taking advantage of the call-by-need language. I very much disagree with Lazlo's comment, that you should use explicit recursion to make the definition valid for call-by-value languages as well. You should take full advantage of the expressive power of your call-by-need language. Otherwise, why not avoid higher-order functions because they are not available in other languages? As Lazlo says, you need a 'lazy mindset' to use this style. It takes time to develop this 'lazy mindset' (just as it takes time to lose it again ;-). To help people understanding and learning this 'lazy mindset', I'd really like to see more examples such as Mark's. If there are more examples, I could collect them on haskell.org.
PS. Why not go all the way
and . uncurry (zipWith (<=)) . id >< tail . dup
with appropriate definitions for dup and >< (prod)?
It is longer, uses more functions and doesn't make the algorithm any clearer. IMHO point-free programming and categorical combinators are not the way to obtain readable programs. Mark uses few standard functions. His definition is more readable than the recursive one, because it is shorter and because it turns implicit control into explicit data structures. Cheers, Olaf -- OLAF CHITIL, Dept. of Computer Science, University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
I have a case where I don't know how to apply laziness well. Consider mutable containers (e.g. STArray or a database on disk). How to iterate over them? I see the following possibilities: * Give up laziness, provide only a conversion to the list of items. Since the conversion is monadic, it must construct the whole list before it returns. Such conversion must be present anyway, especially as this is the only way to ensure that we snapshot consistent contents, and it can be argued that we usually don't really need that much anything more sophisticated, and for some cases we might get values by keys/indices generated in some lazy way. * Use unsafeInterleaveIO and do a similar thing to hGetContents. Easy to use but impure and dangerous if evaluation is not forced early enough. * Invent a lazy monadic sequence: newtype Lazy m a = Lazy {getBegin :: m (Maybe (a, Lazy m a))} (This can't be just type Lazy m a = m (Maybe (a, Lazy m a)) because it would be a recursive type.) It's generic: I can iterate over a collection and stop at any point. But using it is not a pleasure. Some generic operations make sense for this without changing the interface (filter, takeWhile), some don't (filterM - it can't work for arbitrary monad, only for the one used in the particular lazy sequence), and it's needed to have separate versions of some operations, e.g. filterLazy :: Monad m => (a -> m Bool) -> Lazy m a -> Lazy m a which fits neither filter nor filterM. It artificially splits my class design or requires methods implemented as error "sorry, not applicable". * Introduce a stateful iterator, like C++ or Java. This is ugly but would work too. Probably just the simplest version, i.e. getIter :: SomeMutableContainer m a -> m (m (Maybe a)) without going backwards etc. Suggestions? I think I will do the last choice, after realizing that Lazy m a is not that nice, but perhaps it can be done better... -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
participants (4)
-
Laszlo Nemeth -
Marcin 'Qrczak' Kowalczyk -
Mark P Jones -
Olaf Chitil