- Haskell-Cafe - Haskell.org

classes for data structures
by Matthew Pocock 06 Feb '08

06 Feb '08

Hi, I've been working a lot with maps, sets and lists. While the process of getting things out of them is abstracted by foldable, traversable and friends, the process of building one up is not. Would it be possible to have something like: class Buildable b where empty :: b a --makes an empty b with elements of type a insert :: a -> b a -> b a --inserts the new element into the buildable I'm not particularly wedded to the names. It's just that it would be very convenient sometimes to collect data items into e.g. a list or a set, without pushing in some klunky foralled insert function. I see that this is realted to MonadPlus, but the space of possible container classes is wider than that of monads e.g. set. Matthew

5 9

Re: [Haskell] Extensible records: Static duck typing
by Tim Chevalier 06 Feb '08

06 Feb '08

[redirecting to haskell-cafe] On 2/6/08, Barney Hilken <b.hilken(a)ntlworld.com> wrote: > This is what I was trying to do with the wiki page. I stopped because > the only other contributor decided he could no longer contribute, and > I felt I was talking to myself. If we want to be rational about the > design, we need real examples to demonstrate what is genuinely useful, > and I don't have that many of them. It's obvious that records are a language feature that people besides just you care about. And so everybody would benefit from your effort if you chose to continue adding more examples to the wiki page. Records clearly seem to be an important issue if so many people have replied to your thread, and your comment expressing frustration at "arbitrary decisions" getting made about design seems to suggest you have some passion about the issue. On the other hand, if you can't think of real examples offhand, and no one else can either, maybe it's not that important... (Examples don't have to be very complicated to be useful, by the way. Simpler is better.) Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt "If pots couldn't call kettles black, there'd be a lot less talking going on." -- Larissa Ranbom

1 0

weird ghci behavior with gadts and existentials
by Chris Casinghino 06 Feb '08

06 Feb '08

Hi all, I've been playing a bit with gadts and existentials lately, and I have an example where I don't quite understand the behavior of ghc. The expression in question typechecks sometimes in some versions of ghc, depending on where you write it, and not in other versions. Some other people I've asked report not getting any errors, even when using apparently one of the same versions of ghc I checked. If I create a file which contains: > data TypeGADT t where > TyInt :: TypeGADT Int > > data ExpGADT t where > ExpInt :: Int -> ExpGADT Int > > data HiddenTypeExp = forall t . Hidden (TypeGADT t, ExpGADT t) > > weird = case Hidden (TyInt, ExpInt 3) of Hidden (TyInt, e) -> e I am able to :load it into ghci just fine (with -fglasgow-exts) with version 6.8.2. However, if I then copy the line: let weird2 = case Hidden (TyInt, ExpInt 3) of Hidden (TyInt, e) -> e into ghci, I get a type error. In the HEAD version 6.9, I get a type error on the definition of "weird" right away when I :load the file. The type error goes away if I add the line > weird :: ExpGADT Int before the definition of weird. The type error in question is this: <interactive>:1:46: Inferred type is less polymorphic than expected Quantified type variable `t' escapes When checking an existential match that binds e :: ExpGADT t The pattern(s) have type(s): HiddenTypeExp The body has type: ExpGADT t In a case alternative: Hidden (TyInt, e) -> e In the expression: case Hidden (TyInt, ExpInt 3) of Hidden (TyInt, e) -> e So, several questions. 1) Why the discrepancy in behavior between ":load"ing the file and copying in the definition in 6.8.2. It seems like, one way or the other, this should be consistent. 2) Several other people report not getting any errors at all, even people with ghc 6.8.2, one of the versions I tested. What's the "right" behavior? My guess would be that this should cause no type error, even without the type annotation. The GADT pattern match against "TyInt" in the case statement should refine the existential type variable t to Int, so no existential type variables are escaping. Is that right? 3) Is there a bug here? Are there two bugs (one, the typing error, two, the difference between ghc and ghci)? Or, do I just not understand what is going on? Sorry for the length of this email! --Chris Casinghino

2 2

Data.Ord and Heaps (Was: Why functional programming matters)
by apfelmus＠quantentunnel.de 06 Feb '08

06 Feb '08

Stephan Friedrichs wrote: > apfelmus wrote: >> [...] >> Feedback: I think the HeapPolicy thing is too non-standard. The >> canonical way would be to use a MinHeap and let the Ord instance >> handle everything. A MaxHeap can then be obtained via a different >> Ord instance >> newtype Ord a => Reverse a = Reverse { unReverse :: a } >> instance Ord a => Ord (Reverse a) where >> compare = comparing unReverse >> This newtype should be in Data.Ord, of course. Being > > This solution should be used for all collections depending on Ord > instances, including Data.Map, Data.Set and others. As long as I > only include it in my tiny heap package, it is as 'non-standard' as > my approach, isn't it? Yes. I mean "non-standard" in the software-reuse sense, i.e. Ord is for user-defined orderings and should be the only such mechanism in order to enable reuse. In fact, Data.Heap clearly shows that Data.Ord is currently missing functionality. >> Simply setting >> type MaxHeap a = MinHeap (Reverse a) >> is inferior to a "native" MaxHeap since we'd have to pack/unpack >> the Reverse all the time. But a type class for heaps - which >> should be present anyway - can solve that problem: >> class Heap h where >> [...] >> instance Heap MinHeap where ... >> newtype MaxHeap a = M (MinHeap (Reverse a)) >> instance Heap MaxHeap where ... > > I've actually thought about this. Realising MinHeap and MaxHeap is > no problem, but I decided against it, because implementing a custom > order becomes quite complicated: You have to declare an > > newtype MyHeap a = ... > > instance Heap MyHeap where > -- about 10 functions > > instead of just > > data PriorityPolicy > > instance HeapPolicy PP MyPriorityType where > heapCompare = const (comparing priority) Note that the Heap class contains only three primitive operations (empty, insert, viewHead), all the others have default implementations in terms of those three. There is even an underappreciated unfold among them :) toAscList = unfoldr viewHead The structure becomes especially clear by noting that any Heap is defined by just two primitives inject :: Ord a => Maybe (a, Heap a) -> Heap a view :: Ord a => Heap a -> Maybe (a, Heap a) We have inject = maybe empty (uncurry insert) . This is just like lists, except that view . inject ≠ id since view returns the smallest element. However, just that we managed to reduce the number of primitive operations doesn't mean that the policy approach isn't preferable. It needs 0 primitive operations, after all. But as foreshadowed in my reply, it's possible to do policies within Ord. Don't stop thinking about your good idea just because you can start coding :) Here's one way to do it: module Data.Ord where ... class (Ord p a) => OrdPolicy p a where -- the policy p is a type constructor to :: a -> p a from :: p a -> a instance OrdPolicy Identity a where ... newtype Reverse a = Reverse a instance Ord a => Reverse a where compare = flip $ comparing from instance OrdPolicy Reverse a where to = Reverse; from (Reverse x) = x module Data.Heap where ... newtype Heap p a = Heap (MinHeap (p a)) type MaxHeap a = Heap Reverse a class Ord a => Heap h a | h -> a where empty :: h insert :: a -> h -> h viewHead :: h -> Maybe (a, h) instance OrdPolicy p a => Heap (Heap p a) a where ... What I don't like about this is that the policy is not polymorphic in the element types, forcing the Heap class to be multi-parameter. I'd really like to write class (forall a . Ord p a) => OrdPolicy p where but I guess that's (currently) not possible. The original "phantom policy" approach can't quite do this either: module Data.Ord where ... newtype OrdBy p a = OrdBy { unOrdBy :: a } data Reverse instance Ord a => Ord (OrdBy Reverse a) where compare = flip $ comparing unOrdBy module Data.Heap where ... newtype Heap p a = Heap (MinHeap (OrdBy p a)) type MaxHeap a = Heap Reverse a class Heap h where empty :: Ord a => h a insert :: Ord a => a -> h a -> h a viewHead :: Ord a => h a -> Maybe (a, h a) instance (Ord (OrdBy p a)) => Heap (Heap p) where -- forall a? ... However, a distinct advantage of using OrdBy for all ordering policies is that the from and to functions are no longer necessary. All ordering policies use the same type OrdBy which automatically guarantees that from and to are inverse to each other. This would be an informal requirement otherwise, so I think that phantom policies are clearly superior to type constructor policies. Fortunately, this is orthogonal to making Heap a multi- parameter type class and ensuring that OrdBy p a instances are polymorphic in a . >> In conclusion: the ordering policy stuff should not be part of >> Data.Heap, this is a job for Data.Ord. > As mentioned above: This sounds really useful. How about you > propose this to the base-package maintainers? :) What, me? :D Regards, apfelmus

4 4

lazy evaluation
by Peter Padawitz 06 Feb '08

06 Feb '08

Can anybody give me a simple explanation why the second definition of a palindrome checker does not terminate, although the first one does? pal :: Eq a => [a] -> Bool pal s = b where (b,r) = eqrev s r [] eqrev :: Eq a => [a] -> [a] -> [a] -> (Bool,[a]) eqrev (x:s1) ~(y:s2) acc = (x==y&&b,r) where (b,r) = eqrev s1 s2 (x:acc) eqrev _ _ acc = (True,acc) pal :: Eq a => [a] -> Bool pal s = b where (b,r) = eqrev' s r eqrev' :: Eq a => [a] -> [a] -> (Bool,[a]) eqrev' (x:s1) ~(y:s2) = (x==y&&b,r++[y]) where (b,r) = eqrev' s1 s2 eqrev' _ _ = (True,[]) Peter

4 4

fmap vs. liftM
by Felipe Lessa 06 Feb '08

06 Feb '08

Hi there, Reading http://www.haskell.org/haskellwiki/Things_to_avoid I found an interesting saying: "By the way, in the case of IO monad the Functor class method fmap and the Monad based function liftM are the same." I always tought that prop :: (Functor m, Monad m, Eq (m b)) => (a -> b) -> m a -> Bool prop f x = fmap f x == liftM f x was True regardless of 'm'. Is there any exception? If so, why? I've even done s/fmap/liftM/g and s/liftM/fmap/g in the past for consistency =). Thanks! -- Felipe.

7 11

Linear algebra
by Jon Harrop 06 Feb '08

06 Feb '08

Has anyone written anything on the use of FP (e.g. point free style) in linear algebra problems? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e

3 2

bimap 0.2
by Stuart Cook 06 Feb '08

06 Feb '08

I've updated the bimap package to version 0.2. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bimap-0.2 The main difference is a pretty comprehensive interface shakeup: the Either variants have been dropped, all L variants have had the L removed from their name, and a few functions have been curried. The end result is an interface much closer to that of Data.Map. (This also means that 0.2 isn't backwards-compatible.) In addition, the package now supports GHC 6.8, and has a few more tests in the test suite. Stuart

5 9

Parsec3 stream properties
by Philippa Cowderoy 06 Feb '08

06 Feb '08

I'm having a little difficulty finding full properties for Parsec3's Stream class, largely because I don't want to overspecify it with regard to side-effects. Here's the class: > class Stream s m t | s -> t where > uncons :: s -> m (Maybe (t,s)) The idea is that: * unfoldM uncons gives the [t] corresponding to the stream * Assuming no relevant side-effects, unconsing the same value twice will yield the same result What's a relevant side-effect? Well, that's up to the stream and the monad it's built in - but unconsing once shouldn't affect the result of unconsing a second time unless you've found something fiendishly clever that I haven't thought of. Using stream mutability to implement a programming language from within the parsing monad is not a good idea, though no doubt someone'll do it anyway! -- flippa(a)flippac.org Society does not owe people jobs. Society owes it to itself to find people jobs.

1 0

Re: [Haskell-cafe] Mutable arrays
by John Lato 06 Feb '08

06 Feb '08

At least for file processing, I don't think the lazy solution is as bad as some people on this list indicate. My solution was to define a function processAudioFile :: (Handle, Handle) -> (ASig -> ASig) -> IO (), similar to interact. The function reads from the first handle and writes to the second (the problem domain requires two separate files). Contents of the first are read into a lazy bytestring with hGetContents (from Data.ByteString.Lazy), decoded into an ASig (which in the current version is actually a tuple of a list and an Int of the total length, but I'm reworking this into a monad), and processed. The processed list is then encoded back into a bytestring and written with hPut. I then stick the whole thing in a bracket to open and close the filehandles, and call the bracketed function when I'm ready to do processing. I'm pretty happy with this solution, for several reasons: 1. The actual processing code remains purely functional. 2. I didn't have to write imperative-style looping constructs. 3. Handles get closed after use (even with exceptions, thanks to bracket). 4. Because all IO, processing, and writing is encapsulated in one function, everything happens sequentially as it's supposed to, so I don't get exceptions about lazy filehandles being closed. 5. Performance has been good. Memory usage is lower than expected, and it's fairly fast (at least when I remember to use a non-profiled version). I've tested this approach with wave files into the 100's of MB so far. Perhaps not quite as fast as optimized C, but good enough for me. I'm not quite sure how to get around the problem of getElems being strict, though. I do have one idea, but I don't know how it would work in practice: -- let ary_max = foldl1' max $ elems $ unsafeFreeze myArray If you use a boxed array type (IOArray or STArray) for myArray, and compiled with GHC, no copying is necessary (you may need to use type annotations to guarantee this). Then use the foldl' function to get array_max, and map it onto the original mutable array. I think it would be safe provided that you calculate ary_max before you start to modify the array, which is true for normalization. It's worth a try, anyway. John Lato > > Changing the subject slightly, I once wrote code in Concurrent Clean that > > filtered a file that was larger than the available memory on my PC. I did > > this by creating a function that returned the contents of the original file > > as a lazy list. Then, I created functions to process the list and write the > > processed list to a results file. The code was not imperative at all. The > > function that wrote the results file forced the evaluation of the lazy list. > > As the lazy list was consumed, the contents of the original file were read. > > Is this possible with Monads in Haskell? > > Yes, using hGetContents, which is considered bad practice by many > people here. The problem is that hGetContents breaks referential > transparency, and I suspect that whatever Clean does to lazily read > files also does (though I can't be sure, I haven't looked in any > detail at uniqueness types). That is, the contents of the returned > list depend on when you read it, which is not allowed in a > referentially transparent language. > > The same applies to your problem. getElems cannot return a lazy list > of elements*, because what if the array were changed between the point > that you did the getElems and the point you required the element. So > it seems that actually specifying the order of evaluation using an > imperative-style loop is the only pure way to do this. > > * Well, it could, but it would require some cleverness like > copy-on-write logic under the hood.

2 2