February 2008 - Haskell-Cafe

Mutable arrays
by Jeff φ 07 Feb '08

07 Feb '08

Hello, I'm trying to write code that will take a mutable 2D array and normalize it by dividing all elements by the largest element. I managed to write code to do this, but it seems overly complex. I could write something much simpler in Clean or C++. Most likely, my code is complex because I don't have any experience with mutable arrays in Haskell. I couldn't find any tutorials on the Internet. I'd be grateful for suggestions on simplifying the following code. Thanks. {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception #-} -- normalize_ary This takes a mutable array. Determines the largest -- element in the array (max_elem) and then divides every element by -- max_elem. normalize_ary :: (Num t1, Num t, Ix t, Ix t1, MArray a e t2, Ord e, Fractional e, Enum t, Enum t1) => a (t, t1) e -> t2 () normalize_ary ary = do -- The following two commented out lines of code show my first -- attempt at determining a value for max_elem. However, this -- produces a stack overflow. -- elem_ary <- getElems ary -- let max_elem = foldl1 max elem_ary max_elem <- calc_max_2d_elem ary max_elem `seq` map_in_place_2d_arr (\x -> x / max_elem) ary map_in_place_2d_arr :: (MArray a e t, Enum t2, Enum t1, Ix t1, Ix t2) => (e -> e) -> a (t1, t2) e -> t () map_in_place_2d_arr fn arr = ret where ret = do ((i1,j1),(i2,j2)) <- getBounds arr ( mapM_ (\i -> do v <- readArray arr i writeArray arr i (fn v) ) [(i,j) | i <- [i1..i2], j <- [j1..j2]]) calc_max_2d_elem :: (Ord t, MArray a t t1, Ix t2, Ix t3, Num t3, Num t2) => a (t3, t2) t -> t1 t calc_max_2d_elem arr = do m <- readArray arr (0,0) (_,(i_max, j_max)) <- getBounds arr let calc_max_loop arr m (i,j) | j == j_max = return m | otherwise = do e <- readArray arr (i,j) let m2 = max e m m2 `seq` calc_max_loop arr m2 nxt_idx where nxt_idx | i == i_max - 1 = (0,j+1) | otherwise = (i+1,j) calc_max_loop arr m (0,0)

8 12

Why is this so inefficient?
by Jefferson Heard 06 Feb '08

06 Feb '08

I thought this was fairly straightforward, but where the marked line finishes in 0.31 seconds on my machine, the actual transpose takes more than 5 minutes. I know it must be possible to read data in haskell faster than this. I'm trying to read a 100MB comma delimited file. I've tried both CSV modules, and these take even longer to read the file. Is there some general best-practice for reading and parsing large amounts of data that I'm not aware of? I have tried, by the way, a couple of things, including putting a bang (!) before row in transposeRow and using foldr instead of foldl', but that didn't change anything other than force me to increase the stack size to 100M on the command line. I'm running in the profiler now, and I'll update this, but I thought I would check and see if my head was on remotely straight to begin with. -- Jeff --- module ColumnMajorCSV where import qualified Data.ByteString.Char8 as S import qualified Data.Map as M import qualified Data.List as L transposeRow cols row = zipWith (:) row cols transposeCSV :: [[S.ByteString]] -> M.Map String [S.ByteString] transposeCSV (header:rows) = M.fromList (zip (map S.unpack header) spreadsheet) where spreadsheet = L.foldl' transposeRow emptySheet rows emptySheet = take (length header) $ repeat [] dataFromFile :: String -> IO (M.Map String [S.ByteString]) dataFromFile filename = do f <- S.readFile filename print . length . map (S.split ',' $!) . S.lines $ f -- finishes in 0.31 seconds return . transposeCSV . map (S.split ',' $!) . S.lines $ f -- this takes 5 minutes and 6 seconds

4 4

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