June 2016 - Haskell-Cafe

Easy type-level math
by Станислав Черничкин 21 Jun '16

21 Jun '16

With DataKinds and TypeOperators and GHC.TypeLits and, probably, KindSignatures I have: test :: (KnownNat i, KnownNat (i + 4)) => MyType i ((i + 4) + 4) and it's typecheck perfectly. But what I really want to have is: test :: (KnownNat i) => MyType i (i +8) and it does not typecheck. Does not ((i + 4) + 4) == (i +8)? Does not (KnownNat i) implies (KnownNat (i + 4))? Did I miss something about Haskell? -- Thanks, Stanislav Chernichkin.

2 2

Programming in Haskell - 2nd Edition
by Graham Hutton 21 Jun '16

21 Jun '16

Dear all, I'm delighted to announce that the 2nd edition of Programming in Haskell will be published in August 2016! The new edition has been extensively updated and expanded to include recent and more advanced features of Haskell, new examples and exercises, selected solutions, and freely downloadable lecture slides and example code. Further details, including how to preorder and obtain inspection copies, are provided below. Best wishes, Graham ================================================================= *** BOOK ANNOUNCEMENT *** Programming in Haskell - 2nd Edition Graham Hutton, University of Nottingham Cambridge University Press, August 2016 320 pages, 120 exercises, ISBN 9781316626221 http://tinyurl.com/PIH-2e ================================================================= DESCRIPTION: Haskell is a purely functional language that allows programmers to rapidly develop clear, concise, and correct software. The language has grown in popularity in recent years, both in teaching and in industry. This book is based on the author's experience of teaching Haskell for more than twenty years. All concepts are explained from first principles and no programming experience is required, making this book accessible to a broad spectrum of readers. While Part I focuses on basic concepts, Part II introduces the reader to more advanced topics. This new edition has been extensively updated and expanded to include recent and more advanced features of Haskell, new examples and exercises, selected solutions, and freely downloadable lecture slides and example code. The presentation is clean and simple, while also being fully compliant with the latest version of the language, including recent changes concerning applicative, monadic, foldable, and traversable types. ================================================================= CONTENTS: Foreword Preface Part I. Basic Concepts: 1. Introduction 2. First steps 3. Types and classes 4. Defining functions 5. List comprehensions 6. Recursive functions 7. Higher-order functions 8. Declaring types and classes 9. The countdown problem Part II. Going Further: 10. Interactive programming 11. Unbeatable tic-tac-toe 12. Monads and more 13. Monadic parsing 14. Foldables and friends 15. Lazy evaluation 16. Reasoning about programs 17. Calculating compilers Appendix A. Selected solutions Appendix B. Standard prelude Bibliography Index ================================================================= AUTHOR: Graham Hutton is Professor of Computer Science at the University of Nottingham. He has taught Haskell to thousands of students and received numerous best lecturer awards. Hutton has served as an editor of the Journal of Functional Programming, Chair of the Haskell Symposium and the International Conference on Functional Programming, and Vice-Chair of the ACM Special Interest Group on Programming Languages, and he is an ACM Distinguished Scientist. ================================================================= FURTHER DETAILS: The following web page includes details for how the book can be preordered, and how lecturers can obtain inspection copies: http://tinyurl.com/PIH-2e ================================================================= This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham. This message has been checked for viruses but the contents of an attachment may still contain software viruses which could damage your computer system, you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

1 0

Where am I going wrong with my bounding box function?
by Michael Litchard 20 Jun '16

20 Jun '16

I am writing a bounding box module for the octree <https://github.com/BioHaskell/octree/tree/master> library. You can find my branch here <https://github.com/mlitchard/octree/tree/MBB>. In the function below, I try to make explicit the implicit bounding boxes of an Octree. The problem is, not all bounding boxes are valid. This is the function in question, followed by a way to replicate the problem in ghci. explicateMBB :: (BBox3, Octree a) -> [BBox3] explicateMBB (mbb, (Leaf _)) = [mbb] explicateMBB (mbb, (Node { split = split', nwu = nwu', nwd = nwd', neu = neu', ned = ned', swu = swu', swd = swd', seu = seu', sed = sed' })) = mbb:concatMap explicateMBB octList where octList = zip boxList children boxList = [swdBox, sedBox, nwdBox, nedBox, swuBox, seuBox, nwuBox, neuBox] children = [swd',sed',nwd',ned',swu',seu',nwu',neu'] swdBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (minX mbb) (minY mbb) (minZ mbb) neuCorner = Vector3 (v3x split') (v3y split') (v3z split') sedBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (v3x split') (minY mbb) (minZ mbb) neuCorner = Vector3 (maxX mbb) (v3y split') (minZ mbb) nwdBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (minX mbb) (v3y split') (minZ mbb) neuCorner = Vector3 (v3x split') (maxY mbb) (v3z split') nedBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (v3x split') (v3y split') (minZ mbb) neuCorner = Vector3 (maxX mbb) (maxY mbb) (v3z split') swuBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (minX mbb) (minY mbb) (v3z split') neuCorner = Vector3 (v3x split') (v3y split') (maxZ mbb) seuBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (v3x split') (minY mbb) (v3z split') neuCorner = Vector3 (maxX mbb) (v3y split') (maxZ mbb) nwuBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (minX mbb) (v3y split') (v3z split') neuCorner = Vector3 (v3x split') (maxY mbb) (maxZ mbb) neuBox = bound_corners swdCorner neuCorner where swdCorner = Vector3 (v3x split') (v3y split') (v3z split') neuCorner = Vector3 (maxX mbb) (maxY mbb) (maxZ mbb) To replicate problem: git clone https://github.com/mlitchard/octree.git git checkout MBB stack ghci In ghci, do the following : :m + Data.List Data.Vector.Class System.Random System.Random.Shuffle Data.BoundingBox.B3 let infinity = (read "Infinity") :: Double let swdCorner = Vector3 (-infinity) (-infinity) (-infinity) let neuCorner = Vector3 (infinity) (infinity) (infinity) let rbb = bound_corners swdCorner neuCorner xGen <- getStdGen yGen <- newStdGen zGen <- newStdGen let xPoints = shuffle' [-256 .. 256] 513 xGen let yPoints = shuffle' [-256 .. 256] 513 yGen let zPoints = shuffle' [-256 .. 256] 513 zGen let xPoints' = map fromInteger xPoints :: [Double] let yPoints' = map fromInteger yPoints :: [Double] let zPoints' = map fromInteger zPoints :: [Double] let tup513 = zip3 xPoints' yPoints' zPoints' let construct_vect = (\(x,y,z) -> Vector3 x y z) let vect513 = map construct_vect tup513 let pre_oct513 = zip vect513 [1 .. 513] let octree513 = fromList pre_oct513 length $ filter (== False) $ map isValidMBB $ explicateMBB (rbb,octree513) The answer will be 9, but should be 0. I feel like one of the fooBox where clauses is wrong, but I have gone over each one several times, and I am not seeing which one it is. If you needed a visual aid like I did, I found this pic <https://geidav.files.wordpress.com/2014/08/full_octree.png?w=820> to be helpful. My sample does 2 subdivisions. Any insight into what is going wrong would be appreciated.

1 0

AFL + Haskell
by Krzysztof Skrzętnicki 20 Jun '16

20 Jun '16

Hello, There was an interesting post today [1] on Hacker News about fuzzing Rust with american-fuzzy-lop (AFL). Interestingly the AFL instrumentation gets applied as LLVM pass. I started to wonder if it would be possible to do the same with Haskell binaries? I know there are plenty of tools designed specifically for Haskell but still it might be interesting to see how AFL performs in this setting. Cheers, Krzysztof Skrzętnicki [1] https://news.ycombinator.com/item?id=11936983

1 0

How to avoid expensive and unnecessary type conversions?
by David Fox 20 Jun '16

20 Jun '16

Suppose you have a class ListLike (which you do have, actually) and it has methods for operations on types that are like lists, and in particular it has a method fromListLike which converts any ListLike value to any other: fromListLike :: ListLike full' item => full' -> full the default implementation of this is simply fromListLike = fromList . toList but this means that if you happen to apply fromListLike to a value which is already the desired type, two unnecessary and possibly expensive conversions take place. My question is, how can one write code that implements fromListLike in such a way that when the two type parameters are the same type it just uses fromListLike = id I've thought about using a class Convert a b class and writing an instance for every pair of ListLike instances. I haven't convinced myself this would work, and if it does it means that adding a new instance involves writing a bunch of Convert instances. Maybe one could somehow have a default implementation (fromList . toList) but then you run into overlapping instances. Anyone have better ideas about any of this? Hopefully I'm missing something dead simple...

2 2

ST Vector / STRef -- Performances and allocation
by Guillaume Bouchard 20 Jun '16

20 Jun '16

Hello. I read a reddit post [0] which ends in a debate about haskell performances. Someone gives a C implementation which runs in 15ms on some dataset. I wanted to learn about mutable vector and ST and got something in haskell which runs in 50ms. Code is here [1]. [0] https://www.reddit.com/r/haskell/comments/4ojsn0/counting_inversions_haskel… [1] https://github.com/guibou/inversionsCount/blob/syntax/inversions.hs When I'm profiling the code, I'm surprised to see more than 50% of the %alloc in function which, from my point of view, must not allocate. For example, this function : inc :: forall s. STRef s Int -> ST s () inc v = modifySTRef' v (+1) Is responsible for 10% of the allocation in this program. I was hoping that the "unboxing magic" of GHC may have replaced my Int somewhere by an unboxed one, but I guess the allocation means that the STRef is somehow pointing to a heap allocated Int. Do you know a way to remove theses allocations? As a second question, if you see any other way to improve this implementation, I'll be happy to learn something new ;) Finally, if you read my code, you'll see that I implemented a small DSL around ST / STRef / MVector to make my main function more readable. How do people write readable code in real life ? Especially, I was annoyed when I tried to convert this piece of C code : if (x1 < mid && (x2 == sz || tmp[x1] <= p[x2])) { a; } else { b; } In my haskell code, x1, x2 are STRef, and tmp and p are MVector. This was highly painful to write in haskell and I had to write something such as: x1 <- readSTRef x1' x2 <- readSTRef x2' cond <- if x1 < mid then if x2 == sz then return True else do tmp_x1 <- Vector.read tmp x1 p_x2 <_ Vector.read p x2 return (tmp_x1 <= p_x2) else return False if cond then a else b This is painful, complex and error prone, so is there another solution ? Thank you.

5 8

Problem binding GEGL library
by nek0 19 Jun '16

19 Jun '16

Hello fellow haskellers, I am currently working on Haskell bindings to the GEGL [0] library. Since it's my first time working with the FFI and the whole idea of binding a library into Haskell, I have now run into a problem I can't resolve myself. The GEGL headers expose a function "gegl_buffer_iterator_new" which returns an iterator over a selected area in a buffer. This iterator contains a float pointer with pixel data. My problem is to make the iterator and the data it contains accessible to Haskell and to iterate over it. Can someone of you please help me with this problem? One of my initial thoughts was to wrap it into a monad, but I am totally inexperienced with that. My project can be found on my Github profile [1]. Many thanks in advance, nek0 links: [0]: http://www.gegl.org/ [1]: https://github.com/nek0/gegl

2 1

My responses to challenge problems in Bartosz Milewski's "Category Theory for Programmers", thru Ch. 10.
by David Banas 18 Jun '16

18 Jun '16

Hi all, I just finished chapter 10 in Bartosz Milewski’s “Category Theory for Programmers”, and thought I’d share my responses to his challenge problems: https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/… I’d love to hear anyone’s feedback. Cheers, -db

1 0

Trying to test natural transformations, in Haskell.
by David Banas 18 Jun '16

18 Jun '16

Got it: {-# LANGUAGE Rank2Types AllowAmbiguousTypes FlexibleContexts #-} type NatTran f f' a = (Functor f, Functor f') => f a -> f' a to_assert :: (Functor f, Functor f', Eq (f' b)) => (a -> b) -> NatTran f f' a -> NatTran f f' b -> f a -> Bool to_assert g h h' f = (fmap g . h) f == (h' . fmap g) f maybe_to_list :: NatTran Maybe [] a maybe_to_list Nothing = [] maybe_to_list (Just x) = [x] test_func :: Num a => a -> (a, a) test_func x = (x, x + 1) success = all (to_assert test_func maybe_to_list maybe_to_list) [Nothing, Just 1] main :: IO () main = do if success then print "Success!" else print "Failure." main Running this code produces: "Success!" ================================================= Hi all, In doing the challenge problems at the end of chapter 10 (Natural Transformations) in Bartosz Milewski’s “Category Theory for Programmers”, I’m trying to write a generic naturality checker: {-# LANGUAGE Rank2Types AllowAmbiguousTypes #-} type NatTran a = (Functor f, Functor f') => f a -> f' a to_assert :: (Functor f, Eq b) => (a -> b) -> NatTran a -> NatTran b -> f a -> Bool to_assert g h h' f = (fmap g . h) f == (h' . fmap g) f which is later made specific to a particular natural transformation: maybe_to_list :: Maybe a -> [a] maybe_to_list Nothing = [] maybe_to_list (Just x) = [x] test_func :: Num a => a -> (a, a) test_func x = (x, x + 1) assertions = map (to_assert test_func maybe_to_list) [Nothing, Just 1] but I’m getting this from ghc: Could not deduce (Functor f0) arising from a use of ‘fmap’ from the context (Functor f, Eq b) bound by the type signature for interactive:IHaskell465.to_assert :: (Functor f, Eq b) => (a -> b) -> interactive:IHaskell465.NatTran a -> interactive:IHaskell465.NatTran b -> f a -> Bool at :2:14-83 The type variable ‘f0’ is ambiguous Note: there are several potential instances: instance Monad m => Functor (Data.Vector.Fusion.Bundle.Monadic.Bundle m v) -- Defined in ‘Data.Vector.Fusion.Bundle.Monadic’ instance Functor Data.Vector.Fusion.Util.Box -- Defined in ‘Data.Vector.Fusion.Util’ instance Functor Data.Vector.Fusion.Util.Id -- Defined in ‘Data.Vector.Fusion.Util’ ...plus 27 others In the first argument of ‘(.)’, namely ‘fmap g’ In the expression: fmap g . h In the first argument of ‘(==)’, namely ‘(fmap g . h) f’ Can anyone offer some advice? Thanks, -db

2 1

How to spot Monads, Applicatives ...
by martin 18 Jun '16

18 Jun '16

Hello all, I am at a stage, where I can use some of the Monads and Applicatives which are out there. But I hardly ever wrote my own instances. I am curious to learn about the thought processes which lead to the insight "hey that can be written nicely as an Applicative Functor" I suppose you can write everything without these type classes. Is it a promising approach to try without and then spot an element of repetition and factoring out that naturally leads to one of these typeclasses? Paticularly I am having difficulties with the *->* instances. E.g. why is the state "s" in the state monad the fixed type and the "a" the type parameter? When I am writing state code without the State monad the two look like equal candidates. Why not have "State a" monad, which threads an a-typed value and spits out states? While we're at it: would someone be so kind and explain what exactly is meant by an "effect"? I know that in haskell this is not the same as a "side effect" as there are no side-effects in haskell.

6 11