News aggregator

Typed Holes for Beginners

Haskell on Reddit - Wed, 02/18/2015 - 2:22am
Categories: Incoming News

GHC Weekly News - 2015/02/17

Haskell on Reddit - Wed, 02/18/2015 - 2:14am
Categories: Incoming News

Demystifying Type Classes

Haskell on Reddit - Tue, 02/17/2015 - 11:54pm
Categories: Incoming News

The GHC Team: GHC Weekly News - 2015/02/17

Planet Haskell - Tue, 02/17/2015 - 10:06pm

Hi *,

It's time for the GHC weekly news. It's been particularly quiet the past week still, and the ghc-7.10 branch has been quite quiet. So the notes are relatively short this week.

This week, GHC HQ met up to discuss some new stuff:

  • Most of the discussion this week was about particular bugs for GHC 7.10, including getting some tickets fixed like #10058, #8276, and #9968.
  • Since the 7.10 release is getting close, we'll be starting up a new status page about GHC 7.12 (and probably get started writing things for the HCAR report in May) and what our plans are soon. Watch this space!

As usual, we've had a healthy amount of random assorted chatter on the mailing lists:

Some noteworthy commits that went into ghc.git in the past week include:

Closed tickets the past week include: #10047, #10082, #10019, #10007, #9930, #10085, #10080, #9266, #10095, and #3649.

Categories: Offsite Blogs

Haskell Weekly News

haskell-cafe - Tue, 02/17/2015 - 8:55pm
Welcome. Here are this week's picks: - Scott Turner <http://ghc.haskell.org/trac/ghc/ticket/8539#comment:25> proffered a solution in getting exponentiation of complex numbers right, which includes an at-a-glance table to see if everything's sane. - GHC is unsound! <https://mail.haskell.org/pipermail/ghc-devs/2015-January/008189.html> It has a type safety leak. Iavor Diatchki <https://mail.haskell.org/pipermail/ghc-devs/2015-February/008269.html> is hard at work plugging the hole. - Richard Eisenberg <https://mail.haskell.org/pipermail/ghc-devs/2015-February/008271.html> discovered that Debug.Trace.traceStack does a better job debugging GHC than pprTrace. - The curtain is pulled back on the new face of www.haskell.org. Chris Done designed it, Gershom Bazerman announced it, and unsung heroes migrated it and kept it running under the flash crowd onslaught. The raves include: - This is far more welcoming and user-friendly, especially to those who mi
Categories: Offsite Discussion

Seeking an active maintainer for 'directory'

libraries list - Tue, 02/17/2015 - 8:47pm
The 'directory' package could use an active maintainer. Currently, the package falls to the Core Libraries Committee for maintenance, but we've had a number of issues accrete for the directory package over the last six months or so, which need some attention to detail and a good understanding of cross-platform issues. Is anybody interested in nominating themselves for this role? -Edward _______________________________________________ Libraries mailing list Libraries< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Categories: Offsite Discussion

Neil Mitchell: nub considered harmful

Planet Haskell - Tue, 02/17/2015 - 3:00pm

Summary: Don't use nub. A much faster alternative is nubOrd from the extra package.

The Haskell Data.List module contains the function nub, which removes duplicate elements. As an example:

nub [1,2,1,3] == [1,2,3]

The function nub has the type Eq a => [a] -> [a]. The complexity of take i $ nub xs is O(length xs * i). Assuming all elements are distinct and you want them all, that is O(length xs ^ 2). If we only have an Eq instance, that's the best complexity we can achieve. The reason is that given a list as ++ [b], to check if b should be in the output requires checking b for equality against nub as, which requires a linear scan. Since checking each element requires a linear scan, we end up with a quadratic complexity.

However, if we have an Ord instance (as we usually do), we have a complexity of O(length xs * log i) - a function that grows significantly slower. The reason is that we can build a balanced binary-tree for the previous elements, and check each new element in log time. Does that make a difference in practice? Yes. As the graph below shows, by the time we get to 10,000 elements, nub is 70 times slower. Even at 1,000 elements nub is 8 times slower.


The fact nub is dangerous isn't new information, and I even suggested changing the base library in 2007. Currently there seems to be a nub hit squad, including Niklas Hambüchen, who go around raising tickets against various projects suggesting they avoid nub. To make that easier, I've added nubOrd to my extra package, in the Data.List.Extra module. The function nubOrd has exactly the same semantics as nub (both strictness properties and ordering), but is asymptotically faster, so is almost a drop-in replacement (just the additional Ord context).

For the curious, the above graph was generated in Excel, with the code below. I expect the spikes in nub correspond to garbage collection, or just random machine fluctuations.

import Control.Exception
import Data.List.Extra
import Control.Monad
import System.Time.Extra

benchmark xs = do
n <- evaluate $ length xs
(t1,_) <- duration $ evaluate $ length $ nub xs
(t2,_) <- duration $ evaluate $ length $ nubOrd xs
putStrLn $ show n ++ "," ++ show t1 ++ "," ++ show t2

main = do
forM_ [0,100..10000] $ \i -> benchmark $ replicate i 1
forM_ [0,100..10000] $ \i -> benchmark [1..i]
Categories: Offsite Blogs

Very large data structures in the heap

haskell-cafe - Tue, 02/17/2015 - 12:05pm
I have a function that builds a (cyclic) data structure for searching text. The resulting object can be serialized and re-built. Real-world problems would, however, result in a tree with about 10^9 nodes. I take it that standard data type declarations are not very memory-efficient, so my (fully evaluated) search tree would not fit into memory as a heap object. Its serialised form should be of tractable size, e.g. by storing an array of labels and the tree structure as a bit array of parentheses. I'd like to separate serialization (IO) from traversal of the stucture (pure), but how can one avoid the entire heap object from being built? Can lazyness be exploited? Olaf
Categories: Offsite Discussion

Overloadable list type notation

libraries list - Tue, 02/17/2015 - 6:30am
I had an idea whose goal is to ease people into Foldable, Traversable, etc. There could be a notation that shows the generalization that is occurring. map :: Functor [_] => (a -> b) -> [a] -> [b] This means that the syntax for the list type is now syntax for the variable created by the Functor constraint. Adding such a thing to the language is probably not a good idea, but someone might possibly like such a notation for pedagogy. Of course, it will be pointed out that a Functor is not just a container. But Foldable is sometimes expressed as "anything that toList can be called on", so it should make sense there. Greg Weber _______________________________________________ Libraries mailing list Libraries< at >haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Categories: Offsite Discussion

Type-based lift and the burden of type signatures

Haskell on Reddit - Tue, 02/17/2015 - 5:57am

So I was thinking about using /u/roche's Type-based lift for a monad transformer I'm writing, but I have a qualm. Or possibly a quibble.

With the traditional MonadReader typeclass, type inference seems to work pretty well, allowing me to run simple Readers without type annotation:

λ runReader (Control.Monad.Reader.ask) 0 0

However, the same can't be said of the version from Type-based lift:

λ runReader (TypeBasedLift.Reader.ask) 0 <interactive>:237:1: Could not deduce (MonadReaderN (Find (ReaderT a) (ReaderT r0 Identity)) a (ReaderT r0 Identity)) arising from the ambiguity check for ‘it’ from the context (MonadReaderN (Find (ReaderT a) (ReaderT r Identity)) a (ReaderT r Identity), Num r) bound by the inferred type for ‘it’: (MonadReaderN (Find (ReaderT a) (ReaderT r Identity)) a (ReaderT r Identity), Num r) => a at <interactive>:237:1-38 The type variable ‘r0’ is ambiguous When checking that ‘it’ has the inferred type ‘forall r a. (MonadReaderN (Find (ReaderT a) (ReaderT r Identity)) a (ReaderT r Identity), Num r) => a’ Probable cause: the inferred type is ambiguous λ runReader (TypeBasedLift.Reader.ask :: Reader Int Int) 0 0

Here's the version of the code I'm working from:

{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE DataKinds #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE MultiParamTypeClasses #-} module TypeBasedLift.Reader where import Control.Monad.Reader as Trans hiding (MonadReader) import Data.Proxy -- Peano naturals, promoted to types by DataKinds data Nat = Zero | Suc Nat type family Find (t :: (* -> *) -> (* -> *)) (m :: * -> *) :: Nat where Find t (t m) = Zero Find t (p m) = Suc (Find t m) class Monad m => MonadReaderN (n :: Nat) r m where askN :: Proxy n -> m r instance Monad m => MonadReaderN Zero r (ReaderT r m) where askN _ = Trans.ask instance (MonadTrans t, Monad (t m), MonadReaderN n r m, Monad m) => MonadReaderN (Suc n) r (t m) where askN _ = lift $ askN (Proxy :: Proxy n) -- Nice constraint alias type MonadReader r m = MonadReaderN (Find (ReaderT r) m) r m ask :: forall m r . MonadReader r m => m r ask = askN (Proxy :: Proxy (Find (ReaderT r) m))

As quibbles or qualms go, this isn't a huge one. Perhaps it's more of a query. Is the onus of requiring explicit type signatures for monadic values a reason to avoid the technique from Type-based lift? I feel like I usually write signatures anyway, so why not?

However, it feels like I'm shifting work from the library writer (writing typeclass instances) to the library user (writing type signatures), which makes me suspect.

submitted by rampion
[link] [7 comments]
Categories: Incoming News

Primitive Haskell

Haskell on Reddit - Tue, 02/17/2015 - 5:08am
Categories: Incoming News