April 2013 - Haskell-Cafe

Map Reduce spec in Haskell
by John D. Ramsdell 19 Apr '13

19 Apr '13

I'm learning about the Map Reduce computation frequently used with big data. For the fun of it, I decided to write a very high-level spec of Map Reduce. Here is what I came up with. Enjoy. John > module MapReduce where > import Data.List (nub) A high-level specification of Map Reduce as a Haskell program. The program uses lists to represent multisets. As multisets have no implied ordering, the ordering implied by lists in this specification should be ignored. The database is a multiset of key-value pairs. > type Key = String > type Value = String > type Datum = (Key, Value) > type Data = [Datum] A mapper maps a datum to a finite multiset of key-value pairs. > type Mapper = Datum -> Data A reducer takes a key and a multiset of values and produces a finite multiset of values. > type Reducer = (Key, [Value]) -> [Value] A step is a mapper followed by a reducer > type Step = (Mapper, Reducer) A program is a finite sequence of steps > type Program = [Step] The semantics of a program is provided by the run function. > run :: Program -> Data -> Data > run [] d = d > run (s : p) d = > run p (step s d) The three parts of a step are mapping, shuffling, and reducing. > step :: Step -> Data -> Data > step (m, r) d = > let mapped = transform m d > shuffled = shuffle mapped in > reduce r shuffled The first part of a step is to transform the data by applying the mapper to each datum and collecting the results. > transform :: Mapper -> Data -> Data > transform m d = > [p | u <- d, p <- m u] Next, values with common keys are collected. Keys are unique after shuffling. > shuffle :: Data -> [(Key, [Value])] > shuffle d = > [(k, vs) | k <- nub (map fst d), -- nub eliminates duplicate keys > let vs = [v | (k', v) <- d, k' == k]] A reducer is applied to the data associated with one key, and always produces data with that key. > reduce :: Reducer -> [(Key, [Value])] -> Data > reduce r rs = > [(k, v) | (k, vs) <- rs, v <- r (k, vs)]

3 2

how do i get cabal to reinstall dependencies with profiling enabled?
by Anatoly Yakovenko 18 Apr '13

18 Apr '13

3 2

Contravariant applicatives, monads and arrows (was ANN: rematch, an library for composable assertions with human readable failure messages)
by Alejandro Serrano Mena 18 Apr '13

18 Apr '13

Hi, First of all, let me say that this work on matchers is really useful :) Following Roman advice, I'm trying to find a more principled approach that could be useful for this library. It seems that "Match" could easily be converted to Either and thus made into Functor, Applicative, Alternative and Monad. That would allow to write things like: User <$> runMatch (isNot isEmpty) name <*> runMatch (hasItem (is '@')) email However, I'm also thinking about the correct way to "combine" matchers to get bigger matchers. Basically, if I have matchers on every field of a record, can I get a matcher for the entire one? My first idea was to make Matcher a functor. However, what I come was a contravariant functor: given (a -> b) and Matcher b, I can easily construct a Matcher a by running the one in b over this function. So we have: contramap :: (a -> b) -> Matcher b -> Matcher a My first question is: is there any structure similar to applicative functors or monads which work on these kind of contravariant functors? This also brought into my mind to see Matcher a just as functions a -> Match and derive its properties from there. This may give better results that the above mentioned idea of looking it as a -> Either String a, because in this latter case we have a in covariant and contravariant positions and it's difficult to get anything. On the other hand, it seems very easy, from a Matcher a and a Matcher b, to get a Matcher (a,b). This reminds me a bit about arrows, but without output parameters. Does it make sense? I've always been reluctant to arrows because I don't fully understand them, but maybe this is a good moment to learn. Do any of this make sense? I would really like to contribute to this great library! :) 2013/4/16 Tom Crayford <tcrayford(a)gmail.com>: > Roman, > > Thanks for the feedback! I'd originally left the QuickCheck and HUnit > implementations in this library for convenience, thinking that there aren't > going to be many people who care about the transitive dep. But you care, so > I'm happy moving them out of core. I'll release a 0.2 with both the HUnit > and the QuickCheck runners in separate libraries soonish. > > Thanks for the haddock tip and the implementation tips. > > Re the Control namespace, these matchers aren't exclusively a testing tool. > I've been using the core api for other purposes as well (primarily for > validating forms in user interfaces in conjunction with digestive-functors). > I couldn't figure anything better to put it in apart from Control (I > definitely don't want it in Test, even though that's going to be what most > people use it for). I guess it could be in `Data`, but that doesn't sound > much better to me. > > I'm not amazingly strong at building more principled interfaces right now, > so I guess that's something I'll improve on. Are there any concrete > suggestions you have there? I'd *like* these to have an `Alternative` > instance, but making `Applicative`/`Functor` instances is beyond me right > now (I guess I'd have to change the core API for that to work out). > > Tom > > > ...

3 3

Call for Papers: Workshop on Functional Art, Music, Modeling, and Design (colocated with ICFP)
by Brent Yorgey 18 Apr '13

18 Apr '13

====================================================================== FARM 2013: Call for Papers ACM SIGPLAN Workshop on Functional Art, Music, Modeling and Design Boston, Massachusetts, USA 28th September, 2013 (directly after ICFP) http://www.cis.upenn.edu/~byorgey/farm13/ ====================================================================== Scope ----- The functional programming community is largely interested in writing beautiful programs. This workshop is intended to gather researchers and practitioners interested in writing beautiful programs that generate beautiful artifacts. Such artifacts may include visual art, music, 3D sculptures, animations, GUIs, video games, physical models, architectural models, choreographies for dance, poetry, and even physical objects such as VLSI layouts, GPU configurations, or mechanical engineering designs. The framework used need not be purely functional (“mostly functional” is fine); may be based on abstractions such as higher-order functions, monads, arrows, or streams; and may be manifested as a domain specific language or tool. Theoretical foundations, language design, implementation issues, and applications are all within the scope of the workshop. Important dates --------------- - Submissions due: Friday, 14 June 2013, 23:59 UTC-11 (American Samoa time [1]) - Author notification: Thursday, 11 July 2013 - Final papers due: Thursday, 25 July 2013 - Workshop: Saturday, 28 September 2013 (the day after ICFP) [1] http://www.timeanddate.com/worldclock/fixedtime.html?msg=FARM+submissions+d… Proceedings ----------- There will be a formal proceedings published by ACM Press. Accepted papers will be included in the ACM Digital Library; see http://authors.acm.org/main.cfm for information on the options available to authors. Authors are also encouraged to submit auxiliary material for publication along with their paper (source code, data, videos, images, etc.); authors retain all rights to the auxiliary material. Submission details ------------------ We solicit submissions in two categories: - Full papers. A full paper is limited to 12 pages, and will be evaluated according to its relevance, correctness, significance, originality, and clarity. It should explain its contributions, identify what has been accomplished, explain why it is significant, and compare it with previous work. - "Aesthetic applications". An aesthetic application paper is limited to 6 pages, and will be judged primarily on the effective and elegant use of FP to generate aesthetic artifacts (though the criteria for full papers are still relevant). Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines. The text should be in a 9-point font in two columns. Submissions can be made via EasyChair at https://www.easychair.org/conferences/?conf=farm2013 Organizers ---------- Workshop Chair: Paul Hudak Program Chair: Conal Elliott Publicity Chair: Brent Yorgey Program Committee ----------------- Daniel Cukier (AgileAndArt) Conal Elliott (Tabula) (chair) Kathleen Fisher (Tufts University) Richard Gabriel (IBM Research) George Giorgidze (University of Tübingen) Paul Hudak (Yale University) José Pedro Magalhães (University of Oxford) Alex McLean (ICSRiM) John Peterson (Western State Colorado University) Michael Sperber (Active Group) Henning Thielemann (Martin-Luther-Universität Halle-Wittenberg) Brent Yorgey (University of Pennsylvania)

1 0

Re: [Haskell-cafe] Contravariant applicatives, monads and arrows (was ANN: rematch, an library for composable assertions with human readable failure messages)
by Stephen Tetley 18 Apr '13

18 Apr '13

On 16 April 2013 16:12, Alejandro Serrano Mena <trupill(a)gmail.com> wrote: > Hi, > First of all, let me say that this work on matchers is really useful :) > > Following Roman advice, I'm trying to find a more principled approach > that could be useful for this library. It seems that "Match" could > easily be converted to Either and thus made into Functor, Applicative, > Alternative and Monad. That would allow to write things like: > Have you seen Ralf Hinze, Johan Jeuring and Andreas Loeh's paper on Contracts? The found their Contract datatype formed a comonad - at the time this seemed to be one of the few (non-synthetic) uses of comonads.

2 1

ANN: algebraic-classes, conversions between algebraic classes and F-algebras
by Sjoerd Visscher 18 Apr '13

18 Apr '13

Hi all, I'd like to announce a hopefully useful new package: algebraic-classes. In short it provides conversions between algebraic classes and F-algebras, which should make generating instances of certain classes easier. Algebraic classes are classes where every method has the same result type, which is the class parameter. Examples are Num and Monoid. F-algebras are functions of the form f a -> a, with f a functor, which can be called the signature of the algebra. They are equivalent as follows: Algebraic classes are signatures, and the instances of algebraic classes are specific algebras. Take for example the Monoid class: class Monoid a where mempty :: a mappend :: a -> a -> a The equivalent signature would be: data MonoidSignature a = Op_mempty | Op_mappend a a And the list instance instance Monoid [a] where mempty = [] mappend = (++) would be equivalent to the algebra: listAlgebra :: MonoidSignature [a] -> [a] listAlgebra Op_mempty = [] listAlgebra (Op_mappend a b) = a ++ b And there is an obvious monoid algebra for any Monoid instance: evaluate :: Monoid a => MonoidSignature a -> a evaluate Op_mempty = mempty evaluate (Op_mappend a b) = mappend a b Using Template Haskell, the algebraic-classes library can generate signatures and evaluation functions from algebraic classes, and class instances from algebras. Also, for the signatures Functor and Traversable are derived using the DeriveFunctor and DeriveTraversable. That makes it possible to create algebras generically for any signature in certain cases, which together with the conversions means you can generate instances generically. Take tuples for example: if given that both components are instances of a class, then we can create the algebra as follows: algebra :: (Functor f, Class f m, Class f n) => f (m, n) -> (m, n) algebra fmn = (evaluate (fmap fst fmn), evaluate (fmap snd fmn)) And for any applicative functor we can do the same: algebra :: (Traversable f, Applicative g, Class f a) => f (g a) -> g a algebra = fmap evaluate . sequenceA Taken all together, all you have to do to get for example the Monoid instance for Either a b (based on its applicative instance) is: deriveInstance [t| Monoid b => Monoid (Either a b) |] The package lives on Hackage here: http://hackage.haskell.org/package/algebraic-classes And if you have suggestions, issues (the Template Haskell code is far from perfect at the moment) or pull-request, it is also on Github: https://github.com/sjoerdvisscher/algebraic-classes greetings, Sjoerd Visscher

1 0

Haskell missing in web benchmark
by Jeffrey Shaw 18 Apr '13

18 Apr '13

I was excited to see if Warp or Snap was included, but I was sad to see they weren't. If I find time someday, I'll add benchmarks for them, but it will be a long time. If anyone else wants to take a stab at it, that'd be awesome! http://www.techempower.com/blog/2013/03/28/framework-benchmarks/ Jeff

3 2

data types with overlapping component names (in one module)?
by Johannes Waldmann 18 Apr '13

18 Apr '13

What is the current situation: can we have two types with overlapping component names in one module? module M where data T1 = C1 { foo :: Int } data T2 = C2 { foo :: String } It seems not (ghc says: Multiple declarations of 'foo'). This comes close: http://www.haskell.org/ghc/docs/7.6.2/html/users_guide/syntax-extns.html#di… but still requires the definitions to reside in different modules? This is a major pain (it forces me to spread the source over several files), and also a show-stopper when selling Haskell to OO folks, who "naturally" assume that a class also denotes a scope. (And that you could nest them.) Are/were there plans/proposals to address this? - J.W.

4 4

Re: [Haskell-cafe] NaN as Integer value
by wren ng thornton 18 Apr '13

18 Apr '13

On 4/14/13 8:53 PM, Kim-Ee Yeoh wrote: > On Sun, Apr 14, 2013 at 3:28 PM, wren ng thornton <wren(a)freegeek.org> wrote: >> Whereas the problematic >> values due to infinities are overspecified, so no matter which answer you >> pick it's guaranteed to be the wrong answer half the time. >> >> Part of this whole problem comes from the fact that floats *do* decide to >> give a meaning to 1/0 (namely Infinity). > > I'm not sure what you mean about overspecification here, but in > setting 1/0 as +infinity (as opposed to -infinity), there's an easily > overlooked assumption that the limit is obtained "from above" as > opposed to "from below." Setting 1/0 = +inf isn't the problem, or at least not the main one. Of course, there's always the question about which completion of the reals to use--- i.e., whether we have +inf vs -inf, or whether we just have a single point infinity. Rather, the NaN problem comes from trying to resolve things like: inf - inf inf * 0 inf / inf 0 / 0 The overspecification problem I mentioned is that each of these expressions has "too many" solutions. For example, we have the following equations: x * 0 == 0 -- where x is finite inf * y == inf * signum y -- where y /= 0 inf * 0 == ?? x - inf == -inf -- where x is finite inf - y == inf -- where y is finite inf - inf == ?? x / 0 == inf * signum x -- where x /= 0 0 / y == 0 -- where y /= 0 0 / 0 == ?? -- Live well, ~wren

2 1

Derving NFData via Generics from a type that has a vector doesn't work. (was trying to understand out of memory exceptions)
by Anatoly Yakovenko 18 Apr '13

18 Apr '13

-- ok, something in deriving NFData using Generics in a type that has a Vector in it. {-# LANGUAGE DeriveGeneric #-} import Control.DeepSeq import System.IO import GHC.Generics (Generic) import qualified Data.Vector as V import qualified Data.ByteString.Lazy.Char8 as BL scanl' :: NFData a => (a -> b -> a) -> a -> [b] -> [a] scanl' f q ls = q : (case ls of [] -> [] x:xs -> let q' = f q x in q' `deepseq` scanl' f q' xs) -- this runs without blowing up -- main = print $ last $ scanl' (+) (0::Int) [0..] data Simple = Simple (V.Vector Double) deriving (Show, Generic) instance NFData Simple --this blows up main = do let initial = Simple $ V.fromList (take 100 $ repeat 0) sumvs (Simple a) (Simple b) = Simple $ V.zipWith (+) a b print $ last $ scanl' sumvs initial $ repeat $ initial

4 8