December 2009 - Haskell-Cafe

Preconditions as Typeclasses (Was: Re: Mysterious factorial)
by Luke Palmer 30 Dec '09

30 Dec '09

On Wed, Dec 30, 2009 at 11:15 AM, Ralf Hinze <ralf.hinze(a)comlab.ox.ac.uk> wrote: >> I would use: >> >> foldm :: Monoid m => [m] -> m >> >> Which is just a better implementation of mconcat / fold. The reason I >> prefer this interface is that foldm has a precondition in order to >> have a simple semantics: the operator you're giving it has to be >> associative. I like to use typeclasses to express laws. > > That's a valid point. Unfortunately, Haskell is not Coq, so there > is no guarantee that the monoid laws are actually satisfied. And > using a type-class has the downside that you can have only one > instance per type. Maybe, you want to use both `foldm (+) 0' and > `foldm (*) 1'. So the bottom-line is that you should have both > versions. Well, it's a matter of taste, which I'm trying to argue into convention (eg. http://lukepalmer.wordpress.com/2009/07/01/on-the-by-functions/ ). I mean, if you can do foldm (+) 0, it seems quite reasonable to be able to do foldm (-) 0. However, given: newtype Sum a = Sum a instance (Num a) => Monoid (Sum a) where -- (+) is associative with 0 as its identity mempty = Sum 0 mappend (Sum a) (Sum b) = Sum (a + b) It is not so obvious that you can do: newtype Difference a = Difference a instance (Num a) => Monoid (Difference a) where -- (-) is associative with 0 as its identity NOT mempty = Difference 0 mappend (Difference a) (Difference b) = Difference (a - b) Admittedly it is quite a lot more typing, and I do like brevity, but I also like unverified preconditions to be very loud. Once the tech is there, I would like to require a *proof*, but since proving is still hard and Haskell has no support for it, I need some way to document preconditions. I really like that knowing the name and type of a function is enough to use it most of the time, so documentation isn't really a good place for such preconditions. Typeclasses already have the habit of coming with laws, so I take it to the extreme and encode all my preconditions in typeclasses. It is less convenient. But preconditions that are not verified by the typechecker are rare in Haskell code, and proofs of preconditions are subtle, so let's encourage abstraction and documentation of such proofs. In all places except instances, let's be certain that the typechecker does all of our verification work. Luke

1 0

Mysterious factorial
by Artyom Kazak 30 Dec '09

30 Dec '09

Why fact2 is quicker than fact?! fact2 :: Integer -> Integer fact2 x = f x y where f n e | n < 2 = 1 | e == 0 = n * (n - 1) | e > 0 = (f n (e `div` 2)) * (f (n - (e * 2)) (e `div` 2)) y = 2 ^ (truncate (log (fromInteger x) / log 2)) fact :: Integer -> Integer fact 1 = 1 fact n = n * fact (n - 1) I tried to write tail-recursive fact, fact as "product [1..n]" - fact2 is quicker! fact2 1000000 == fact 1000000 - I tested.

6 10

Finally tagless and abstract relational Algebra
by Günther Schmidt 30 Dec '09

30 Dec '09

Hi, I'm still trying to build an *abstract* Relation Algebra using the finally tagless style. My guess is that finally tagless style allows one to create a syntax without any initial dependency to an implementation. Ie. once one has created the syntax in this style one can then proceed to construct terms. So this is my goal, create a syntax for relational algebra, express an abstract relational algorithm in this syntax and worry about implementation / compilation / evaluation *later*. But at least being able to express a correctly typed term. I presume I will need to employ HList at some point, but I'm not entirely certain where. Will I need it at the very beginning, as constrains in the syntax so that only correct abstract terms can be built, or will I need it in on of the interpreters / compilers later? Günther

6 13

Alternatives to type classes.
by Jason Dusek 30 Dec '09

30 Dec '09

Consider the real numbers. They "are" a group. We have an identity element `0', inverses and closure under the associative operation `+'. Group+ = (+, 0, -1 * _) They are another group, too -- the group with `*': Group* = (*, 1, 1 / _) This seems like a real problem with the whole notion of typeclasses -- we can't really say a set/type "is" its extension with some new operations. One road to go on this is to make every extension of the set with new ops a different type; but that seems really horribly inconvenient. I wonder what approaches have been tried here? -- Jason Dusek

3 3

Re: [Haskell-cafe] (liftM join .) . mapM
by gladstein＠gladstein.com 29 Dec '09

29 Dec '09

I couldn't resist the opportunity for some ascii abstract art. Emacs turns the backquoted bits blue. f `o` g = ( f) . g f `oo` g = (o f) . g f `ooo` g = (oo f) . g f `oooo` g = (ooo f) . g f `ooooo` g = (oooo f) . g f `oooooo` g = (ooooo f) . g f `ooooooo` g = (oooooo f) . g f `oooooooo` g = (ooooooo f) . g f `ooooooooo` g = (oooooooo f) . g f `oooooooooo` g = (ooooooooo f) . g f `ooooooooooo` g = (oooooooooo f) . g f `oooooooooooo` g = (ooooooooooo f) . g f `ooooooooooooo` g = (oooooooooooo f) . g f `oooooooooooooo` g = (ooooooooooooo f) . g f `ooooooooooooooo` g = (oooooooooooooo f) . g f `oooooooooooooooo` g = (ooooooooooooooo f) . g f `ooooooooooooooooo` g = (oooooooooooooooo f) . g f `oooooooooooooooooo` g = (ooooooooooooooooo f) . g f `ooooooooooooooooooo` g = (oooooooooooooooooo f) . g f `oooooooooooooooooooo` g = (ooooooooooooooooooo f) . g

1 0

(liftM join .) . mapM
by Tony Morris 29 Dec '09

29 Dec '09

Can (liftM join .) . mapM be improved? (Monad m) => (a -> m [b]) -> [a] -> m [b] -- Tony Morris http://tmorris.net/

9 15

suffix or operands invalid for `push'
by Martijn van Steenbergen 29 Dec '09

29 Dec '09

Hello, Above error is one of those that appear when using GHC on the 64-bit Snow Leopard. I've already patched my /usr/bin/ghc to mention -optc-m32 -opta-m32 -optl-m32. However, the error still occurs when doing 'cabal haddock' in *some* packages. For example, a local project of mine builds just fine, but trying to cabal haddock the happstack-helpers package goes horribly wrong and no documentation is generated. How do I fix this? And why does it happen only in certain packages? Many thanks, Martijn.

2 3

Perhaps you haven't installed the "dyn" libraries
by Gregory Propf 29 Dec '09

29 Dec '09

I'm trying out the dynamic linking in GHC 6.12 and getting this message a lot for different libraries. I assume I need to rebuild them with different ghc options in the cabal files and have tried -shared, -dynamic and -fPIC but with no luck. Is there something I'm missing.

2 1

Configuring cabal install readline on Snow Leopard with MacPorts
by Alexy Khrabrov 29 Dec '09

29 Dec '09

I've tried to do cabal install readline on Snow Leopard with MacPorts and it fails with the infamous: $ cabal install readline ... checking for GNUreadline.framework... checking for readline... no checking for tputs in -lncurses... yes checking for readline in -lreadline... yes checking for rl_readline_version... yes checking for rl_begin_undo_group... no configure: error: readline not found, so this package cannot be built See `config.log' for more details. cabal: Error: some packages failed to install: readline-1.0.1.0 failed during the configure step. The exception was: exit: ExitFailure 1 Googilng shows the usual explanation that Mac'y broken clone interferes; yet I do have MacPorts and readline 6 there. So I try, per fixes recommended, $ cabal install readline --extra-include-dirs=/opt/local/include --extra-lib-dirs=/opt/local/lib ... checking for rl_readline_version... yes checking for rl_begin_undo_group... no ... -- same result. Downloaded the package and do configure manually: ./configure --with-readline-includes=/opt/local/include --with-readline-libraries=/opt/local/lib ... checking for readline in -lreadline... no checking for rl_readline_version... no ... Huh? $ port contents readline ... /opt/local/include/readline/readline.h ... /opt/local/lib/libreadline.5.0.dylib /opt/local/lib/libreadline.5.1.dylib /opt/local/lib/libreadline.5.2.dylib /opt/local/lib/libreadline.6.0.dylib /opt/local/lib/libreadline.6.dylib /opt/local/lib/libreadline.a /opt/local/lib/libreadline.dylib ... How should I properly tell cabal install readline where my readline is? Cheers, Alexy

4 4

ghc 6.12.1 and regex
by David Fox 29 Dec '09

29 Dec '09

Is anyone else seeing this problem: > :m +Text.Regex.Posix > "\250" =~ "\250" :: Bool True > "\250" =~ "[\250]" :: Bool False

2 3