August 2010 - Haskell-Cafe

the overlapping instance that wasn't?
by Michael Vanier 25 Aug '10

25 Aug '10

Hi everyone, Here's some code that's giving me an error message I don't understand: {-# LANGUAGE EmptyDataDecls, MultiParamTypeClasses, UndecidableInstances, FlexibleInstances #-} data Z data S n class Nat n where toInt :: n -> Int instance Nat Z where toInt _ = 0 instance (Nat n) => Nat (S n) where toInt _ = 1 + toInt (undefined :: n) instance (Nat n) => Show n where show _ = show $ toInt (undefined :: n) -- end of code sample When I run this through ghci, I get this: test.hs:19:11: Overlapping instances for Show Int arising from a use of `show' at test.hs:19:11-14 Matching instances: instance Show Int -- Defined in GHC.Show instance (Nat n) => Show n -- Defined at test.hs:18:9-25 In the first argument of `($)', namely `show' In the expression: show $ toInt (undefined :: n) In the definition of `show': show _ = show $ toInt (undefined :: n) Adding OverlappingInstances to the language pragmas fixes the problem. My question is: why is this an overlapping instance? It would make sense if Int was an instance of Nat, but it isn't. Is this just a limitation in the way overlapping instances are identified? Mike

3 2

and from standard Prelude
by Oleg Lobachev 25 Aug '10

25 Aug '10

Hello all, the and function, and :: [Bool] -> Bool is defined in two different ways in the latest Prelude. I would expect it to be > and = foldr (&&) True However, there is a further recursive definition, and it is the one used! See http://haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/src/GHC-List… > #ifdef USE_REPORT_PRELUDE > and = foldr (&&) True > or = foldr (||) False > #else > and [] = True > and (x:xs) = x && and xs > or [] = False > or (x:xs) = x || or xs > > {-# RULES > > "and/build" forall (g::forall b.(Bool->b->b)->b->b) . > > and (build g) = g (&&) True > > "or/build" forall (g::forall b.(Bool->b->b)->b->b) . > > or (build g) = g (||) False > > #-} > #endif Is there any reason for that besides some clever optimizations? I am particularly interested in the behavior of and for infinite lists and these two versions are equivalent in this aspect. Greetings, Oleg

5 7

lazy skip list?
by Evan Laforge 24 Aug '10

24 Aug '10

Is there a data type that's spine lazy like a list, but can be seeked (sought?) efficiently? IntMap and Sequence are spine strict so if you take the head element all the elements are forced even if their contents are not. E.g., 'Sequence.index (Sequence.fromList [0..]) 0' will diverge, but obviously 'head [0..]' won't. I can get what I want from a list of lists where the outer list is is 'iterate (drop n)' on the inner one... this is a kind of skip list, right? It seems like it should be possible to generalize this to multiple levels with increasing skip amounts, then I can seek relatively efficiently and won't force the spine beyond where I seek. Effectively, this is nested list like [[[a]]], where each level above the bottom is something like 'iterate (drop n) level_below'. Alternately, it should also be possible to do something fancy like a self-modifying data structure that constructs its index as you force bits of it, but this would require some hairy unsafePerformIO, I think. Has anyone heard of a data structure like this, either the plain list of lists or the self modifying magic one? Surely efficiently indexing a lazy list is something someone else has thought about? It looks like Luke Palmer's data-inttrie might be doing this, though it's not clear from the documentation. It looks like it lacks emptiness, so it doesn't apply to finite structures. lazyarray looks like it might be doing the magic self-modifying thing, though it wants a a static bounds right off the bat, which isn't much help when the whole point is to avoid having to figure out how long the input is.

5 11

Re: [Haskell-cafe] the overlapping instance that wasn't?
by Michael Vanier 24 Aug '10

24 Aug '10

On 8/24/10 1:54 PM, Bartek Æwik³owski wrote: > Hello Michael, > > This is because instance selection is solely based on instance heads, > it doesn't consider contexts. There's a nice explanation available > here: http://www.haskell.org/haskellwiki/GHC/AdvancedOverlap > > The fix in this case is very easy because there are only two cases > (and you don't want to provide new Nat class instances): > > instance Show Z where > show _ = "0" > > instance Nat n => Show (S n) where > show _ = show $ toInt (undefined :: n) + 1 > > regards, > Bartek Æwik³owski OK, thanks! Mike

1 0

Re: [Haskell-cafe] Fwd: Semantics of iteratees, enumerators, enumeratees?
by John Lato 24 Aug '10

24 Aug '10

> > From: Stephen Tetley <stephen.tetley(a)gmail.com> > > On 24 August 2010 13:00, John Lato <jwlato(a)gmail.com> wrote: > > > This is how I think of them. I particularly your description of them as > a > > foldl with a "pause" button. > > Maybe it would be helpful to consider iteratees along with delimited > > continuations? > > Aren't they closer - in implementation and by supported operations - > to resumptions monads? > > See many papers by William Harrison here: > http://www.cs.missouri.edu/~harrisonwl/abstracts.html > > I'm not familiar with resumption monads. I'll have to read some of the papers and get back to you. John

3 2

ANNOUNCE: Sifflet visual programming language, release 1.1
by gdweber＠iue.edu 24 Aug '10

24 Aug '10

Sifflet-lib 1.1 and sifflet 1.1 are now available on Hackage. Sifflet is a visual, functional programming language and support system for students learning about recursion. Sifflet programmers define functions by drawing diagrams, and the Sifflet interpreter uses diagrams to show how the function calls are evaluated. Sifflet-lib is the library containing many modules of the sifflet application. New in This Release ------------------- - Relaxed versioned dependencies on cairo, gtk, glib (== 0.11.* instead of == 0.11.0) should make it possible to build with slightly newer versions of these libraries (and pango). - Sifflet export to Haskell now removes most unnecessary parentheses. - The module Sifflet.Data.Number is now Data.Number.Sifflet. - Many undocumented API changes in sifflet-lib. (I really hope nobody is using this library for development but me! But if you are, contact me, and I'll send a partial list of the changes.) About Sifflet ------------- Sifflet is a visual, functional programming language intended as an aid for learning about recursion. * A picture explains Sifflet better than words: please see the screenshot showing how to evaluate 3!: http://mypage.iu.edu/~gdweber/software/sifflet/home.html * Features: - Visual editor. - Visual tracer/debugger which shows how recursive and other function calls are evaluated. To support active learning and avoid screen clutter, Sifflet displays only as much of the computation as the user requests. - A carefully crafted tutorial with 31 pictures and about as many pages. - Number, string, and list data types. - A small collection of primitive functions. - Runnable examples of compound functions. - Sifflet functions can be "exported" to Scheme, Python 3, and Haskell. * Download: http://hackage.haskell.org/package/sifflet-lib http://hackage.haskell.org/package/sifflet * Home page: http://mypage.iu.edu/~gdweber/software/sifflet/home.html * Tutorial: http://mypage.iu.edu/~gdweber/software/sifflet/doc/tutorial.html -- ___ ___ __ _ / _ \ / _ \| | | | Gregory D. Weber, Associate Professor / /_\// / | | | /\ | | Indiana University East / /_\\/ /__| | |/ \| | http://mypage.iu.edu/~gdweber/ \____/\_____/\___/\__/ Tel. (765) 973-8420; FAX (765) 973-8550

1 0

Re: ANNOUNCE: enumerator, an alternative iteratee package
by John Lato 24 Aug '10

24 Aug '10

> > From: Magnus Therning <magnus(a)therning.org> > > On 24/08/10 03:47, John Millikin wrote: > [...] > > I would like to avoid hard-coding the error type to SomeException, > because > > it forces libraries to use unsafe/unportable language features (dynamic > > typing and casting). However, given the apparent practical requirement > that > > all iteratees have the same error type, it seems like there's no other > > choice. > > I haven't worked enough with iteratees to have an informed opinion on this, > but I wonder what the pros and cons are of having an error state in the > iteratees at all. In other words, why would this > > data Step a m b > = Continue (Stream a -> Iteratee a m b) > | Yield b (Stream a) > | Error E.SomeException > > be preferred over this > > data Step a m b > = Continue (Stream a -> Iteratee a m b) > | Yield b (Stream a) > > (Maybe with the restriction that m is a MonadError.) > Oleg included the error state to enable short-circuiting of computation, and I guess everyone just left it in. Recently I've been wondering if it should be removed, though, in favor requiring explicit (i.e. explicit in the type sig) exceptions for everything. I'm not sure if that would be more or less complicated. John

4 3

Re: [Haskell-cafe] Re: Fwd: Semantics of iteratees, enumerators, enumeratees?
by John Lato 24 Aug '10

24 Aug '10

I think the big problem with chunking is that many useful iteratees need to be able to inspect the length of the chunk. The most obvious is "drop", but there are many others. Or if not inspect the length, have a new function on the stream "dropReport :: Int -> s -> (s, Int)" which reports how much was dropped. Either way, chunking adds a deal of implementation burden. I suspect that the proper vocabulary for iteratees wouldn't include chunks at all, only single elements. This discussion has prompted me to consider the implications of such an implementation, as it would be much simpler. I have one idea that I think will at least maintain performance for many operations, although there will be performance hits too. If the drawbacks are in areas that aren't particularly useful, though, it may be acceptable. John > From: Conal Elliott <conal(a)conal.net> > > Here's a way I've been tinkering with to think about iteratees clearly. > > For simplicity, I'll stick with pure, error-free iteratees for now, and > take > chunks to be strings. Define a function that runs the iteratee: > > > runIter :: Iteratee a -> [String] -> (a, [String]) > > Note that chunking is explicit here. > > Next, a relation that an iteratee implements a given specification, defined > by a state transformer: > > > sat :: Iteratee a -> State String a -> Bool > > Define sat in terms of concatenating chunks: > > > sat it st = > > second concat . runIter it == runState st . second concat > > where the RHS equality is between functions (pointwise/extensionally), and > runState uses the representation of State directly > > > runState :: State s a -> s -> (a,s) > > (I think this sat definition is what Conrad was alluding to.) > > Now use sat to specify and verify operations on iteratees and to > *synthesize* those operations from their specifications. Some iteratees > might not satisfy *any* (State-based) specification. For instance, an > iteratee could look at the lengths or number of its chunks and produce > results accordingly. I think of such iteratees as abstraction leaks. Can > the iteratee vocabulary be honed to make only well-behaved (specifiable) > iteratees possible to express? If so, can we preserve performance > benefits? > > If indeed the abstraction leaks can be fixed, I expect there will be a > simpler & more conventional semantics than sat above. > > - Conal > > > On Tue, Aug 24, 2010 at 2:55 PM, Conrad Parker <conrad(a)metadecks.org> > wrote: > > > On 24 August 2010 14:47, Jason Dagit <dagit(a)codersbase.com> wrote: > > > > > > > > > On Mon, Aug 23, 2010 at 10:37 PM, Conrad Parker <conrad(a)metadecks.org> > > > wrote: > > >> > > >> On 24 August 2010 14:14, Jason Dagit <dagit(a)codersbase.com> wrote: > > >> > I'm not a semanticist, so I apologize right now if I say something > > >> > stupid or > > >> > incorrect. > > >> > > > >> > On Mon, Aug 23, 2010 at 9:57 PM, Conal Elliott <conal(a)conal.net> > > wrote: > > >> >>> > > >> >>> So perhaps this could be a reasonable semantics? > > >> >>> > > >> >>> Iteratee a = [Char] -> Maybe (a, [Char]) > > >> >> > > >> >> I've been tinkering with this model as well. > > >> >> > > >> >> However, it doesn't really correspond to the iteratee interfaces > I've > > >> >> seen, since those interfaces allow an iteratee to notice size and > > >> >> number of > > >> >> chunks. I suspect this ability is an accidental abstraction leak, > > >> >> which > > >> >> raises the question of how to patch the leak. > > >> > > > >> > From a purely practical viewpoint I feel that treating the chunking > as > > >> > an > > >> > abstraction leak might be missing the point. If you said, you > wanted > > >> > the > > >> > semantics to acknowledge the chunking but be invariant under the > size > > or > > >> > number of the chunks then I would be happier. > > >> > > >> I think that's the point, ie. to specify what the invariants should > > >> be. For example (to paraphrase, very poorly, something Conal wrote on > > >> the whiteboard behind me): > > >> > > >> run [concat [chunk]] == run [chunk] > > >> > > >> ie. the (a, [Char]) you maybe get from running an iteratee over any > > >> partitioning of chunks should be the same, ie. the same as from > > >> running it over the concatenation of all chunks, which is the whole > > >> input [Char]. > > > > > > I find this notation foreign. I get [Char], that's the Haskell String > > > type, but what is [chunk]? I doubt you mean a list of one element. > > > > sorry, that was just my way of writing "the list of chunks" or perhaps > > "the stream of chunks that represents the input". > > > > Conrad. > > > > > > > >> > > >> > I use iteratees when I need to be explicit about chunking and when I > > >> > don't > > >> > want the resources to "leak outside" of the stream processing. If > you > > >> > took > > >> > those properties away, I wouldn't want to use it anymore because > then > > it > > >> > would just be an inelegant way to do things. > > >> > > >> Then I suppose the model for Enumerators is different than that for > > >> Iteratees; part of the point of an Enumerator is to control the size > > >> of the chunks, so that needs to be part of the model. An Iteratee, on > > >> the other hand, should not have to know the size of its chunks. So you > > >> don't want to be able to know the length of a chunk (ie. a part of the > > >> stream), but you do want to be able to, say, fold over it, and to be > > >> able to stop the computation at any time (these being the main point > > >> of iteratees ...). > > > > > > I think I agree with that. > > > Jason > >

2 2

Content Centric Networking
by Tom Hawkins 24 Aug '10

24 Aug '10

Anyone in the Haskell community interested in content-centric networking? Van Jacobson has done a couple of great presentations to introduce CCN [1, 2]. Personally, I find it fascinating what kind of doors could open if we got away from TCP/IP, especially for wireless ad-hoc networking. Parc has open-sourced their experimental CCN protocol, CCNx [3]. I thought it'd be cool to have a Haskell implementation of CCNx, so I started a little hackage project [4]. -Tom [1] http://video.google.com/videoplay?docid=-6972678839686672840# [2] http://www.parc.com/work/focus-area/networking/ [3] http://www.ccnx.org/ [4] http://hackage.haskell.org/package/ccnx/

1 0

Higher-order algorithms
by Max Rabkin 24 Aug '10

24 Aug '10

(Accidentally sent off-list, resending) On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov <ekirpichov(a)gmail.com> wrote: > * Difference lists > I mean that not only higher-order facilities are used, but the essence > of the algorithm is some non-trivial higher-order manipulation. If I'm not mistaken, we can "defunctionalize" difference lists like this: data DList a = Chunk [a] | Concat (DList a) (DList a) fromList = Chunk (<>) = Concat singleton = Chunk . (:[]) empty = Chunk [] toList dl = dl `fold` [] where infixr `fold` fold :: DList a -> [a] -> [a] fold (Concat l r) ys = l `fold` r `fold` ys fold (Chunk xs) ys = xs ++ ys (This implementation has only been lightly tested) And of course, we knew this was possible, since we can compile DLists to first-order machines. I agree that the functional, higher-order presentation is clear and elegant. But is it essential? Also, I'm curious about how this performs relative to the functional version. --Max

2 1