May 2016 - Haskell-Cafe

OAuth2 and OpenID Connect in Haskell
by Luke Taylor 10 May '16

10 May '16

Hello all, I've written a blog article as an introduction to the Haskell project I've been working on, which may be of interest to some people here. It's an OpenID Connect identity provider. http://broch.io/posts/oauth2-openid-connect-haskell/ I'd really welcome any feedback on other/better ways of doing some of things it talks about. Cheers, Luke.

1 0

Re: [Haskell-cafe] Automatic differentiation (AD) with respect to list of matrices in Haskell
by Miguel A. Santos 10 May '16

10 May '16

Awesome! Lots of new info! And more importantly, I got it to work. > > I still need to work on it a bit more, but things seems to be getting > clearer. > > On Sun, May 8, 2016 at 2:25 PM, Moritz Kiefer < > moritz.kiefer(a)purelyfunctional.org> wrote: > >> >> Miguel A. Santos <miguel.a.santos.l(a)gmail.com> writes: >> >> > Thanks a lot for your quick answer. >> > >> > First, I can't get your modifications through: What are Scalar & Mode? >> ghc >> > says type/class not in scope. >> >> Oh sorry you need to import Numeric.AD for that. Mode is a typeclass >> with an associated type called Scalar. You can just think of it as some >> magic that allows you to use constants in your function. >> >> > Yes. I figured out as well. I was only importing its Mode.Reverse as R. > > > >> > Some more questions to help me understand your suggestions below. >> > >> > >> > On Sun, May 8, 2016 at 1:14 PM, Moritz Kiefer < >> > moritz.kiefer(a)purelyfunctional.org> wrote: >> > >> >> >> >> There are two orthogonal errors going on here: >> >> >> >> 1. You need to use auto to embed constants. See the comments at the >> code >> >> below on how to use it. >> >> >> >> Ah, that solves indeed the first problem. Thanks! >> > >> > >> >> 2. You need to wrap [Matrix a] in a newtype. grad requires you to >> >> provide a function f a -> a, however sc2 _ has the type [Matrix a] -> a >> >> so if you replace [] by f you end up with f (Matrix a) -> a which >> >> results in the error you’re seeing. >> >> >> > >> > I've problems following you here. For example this is legit and works >> > grad (\[x,y] -> x^2y^3) [5,7] >> > >> > That is, grad here is taking a function f [a,a] -> a. That seems to >> work as >> > well with sc1 in my example: I do get the rigth gradient. >> >> That function has type [a] -> a which can be rewritten as [] a -> a and >> if you unify [] and f you have f a >> -> a which is exactly what you need. >> >> However in sc2 you have a function of type [Matrix a] -> a which can be >> rewritten as [] (Matrix a) -> a and if you unify f and [] you end up >> with f (Matrix a) -> a. However Matrix a and a are not the same type so >> you get an error. >> >> > I got confused by the expression "[the] function f a -> a": I though the > word 'function' was referring to the symbol 'f'. > > Yet, I still can't follow things completely...uhm, issuing :type grad in > ghci I get > grad > :: (Num a, Traversable f) => > (forall s. > Data.Reflection.Reifies s Numeric.AD.Internal.Reverse.Tape => > f (Numeric.AD.Internal.Reverse.Reverse s a) > -> Numeric.AD.Internal.Reverse.Reverse s a) > -> f a -> f a > > which I'd say could be simplified to > grad :: Num a => ( f Reverse s a -> Reverse s a) -> f a -> f a > > Now, It's not only that I don't see your "grad expects a 'f a -> a' ", but > I don't even see how something like grad (\[x,y]-> x*y) [2,3] fits...or do > I? The notation 'f' seems was misleading me. I'd say what's important is > its type, name Traversable f. [] seems to fit there, isn't? So the first > argument of grad more or less would be what you were referring to ( f a -> > a) , the second it the point to calculate the gradient at (of course a [a], > or, [] a, hence, f a) and it does yield a "vector" (on paper). > Interestingly, its implementation means that grad's output is the same type > the input of the function we want to take its gradient of. > > I think it starts making sense to me now. > > >> >> >> Miguel A. Santos <miguel.a.santos.l(a)gmail.com> writes: >> >> >> >> > mv _ [] = [] >> >> > mv (M []) _ = [] >> >> > mv ( M m ) v = ( dot (head m) v ) : (mv (M (tail m)) v ) >> >> > --- two matrices >> >> >> >> You need explicit type annotations to make this polymorphic here >> because >> >> of the monomorphism >> >> restriction. >> >> >> >> >> > Just for the sake of learning how to use that jargon in this context: >> > which/what is that monomorphism restriction are you referring to? Also, >> > when you say my mbW1 is polymorphic, do you mean, given my definition of >> > it, ghc cannot adscribe it one _unique_ type signature, but that will >> vary >> > depending on the context? >> >> I’m going to refer you to the haskell report [1] for information on the >> monomorphism restriction. By polymorphic I’m referring to the choice of >> a which is now left open. >> >> Thanks!! > > >> >> mbW1 :: Num a => Matrix a >> >> > mbW1 = M $ [[1,0,0],[-1,5,1],[1,2,-3]] >> >> > mbW2 = M $ [[0,0,0],[1,3,-1],[-2,4,6]] >> >> > --- two different scoring functions >> >> >> >> -- Provide a type signature and map auto over the constants >> >> sc1 :: (Floating b, Mode b) => [Scalar b] -> Matrix b -> b >> >> sc1 v m = foldr (+) 0 $ (phi' . (mv m) ) (map auto v) >> >> >> > >> >> -- Provide a type signature, use auto and use the newtype >> >> newtype MatrixList a = MatrixList [Matrix a] deriving >> >> (Functor,Foldable,Traversable) >> >> >> >> sc2 :: (Floating a,Mode a) => [Scalar a] -> MatrixList a -> a >> >> sc2 v [m1, m2] = foldr (+) 0 $ (phi' . (mv m2) . phi' . (mv m1) ) (map >> >> auto v) >> >> >> >> > strToInt = read :: String -> Double >> >> > strLToIntL = map strToInt--- testing >> >> > main = do >> >> > putStrLn $ "mbW1:" ++ (show mbW1) >> >> > putStrLn $ "mbW2:" ++ (show mbW2) >> >> > rawInput <- readFile "/dev/stdin" >> >> > let xin= strLToIntL $ lines rawInput >> >> > putStrLn "sc xin mbW1" >> >> >> >> -- That needs an explicit type annotation because mbW1 is polymorphic >> >> print $ sc1 xin (mbW1 :: Matrix Double) --- ok. = >> >> >> >> uhm...but it doesn't seem to give any problem, especially not after >> using >> > auto...I've still problems getting an intuition on when ghc does need >> "my >> > help" and when it can walk on it own. >> >> Hm maybe you don’t need it after all. I thought I got an error >> locally. Sorry I don’t have any good tip on how to get an >> intuition. I add them when I’m unsure about the type of something myself >> to help me to figure it out and when I get an error. >> >> >> > putStrLn "grad (sc1 xin) mbW1" >> >> > print $ grad ( sc1 xin) mbW1 -- yields an error: expects >> xin >> >> > [Reverse s Double] instead of [Double] >> >> > putStrLn "grad (sc1 [3,5,7]) mbW1" >> >> > print $ grad ( sc1 [3,5,7]) mbW1 --- ok. = >> >> > putStrLn "sc2 xin [mbW1,mbW2]" >> >> > print $ sc2 xin [mbW1, mbW2] >> >> > putStrLn "grad (sc2 [3,5,7) [mbW1,mbW2]" >> >> >> >> -- Use the newtype defined above >> >> print $ grad ( sc2 [3,5,7]) (MatrixList [mbW1, mbW2]) --- >> Error: >> >> see text >> >> >> >> Also as a general recommendation, write your type signatures >> explicitely >> >> at least for top level definitions. >> >> >> > >> > What do you mean by "top level" definitions? --again, just a side >> comment >> > to fine-tune my jargon registers. >> >> Top level definitions are the definitions in your module that are not in >> a let or where. So basically everything that’s accessible from other >> definitions outside of the current one. >> >> > I still have to learn my way through all types. Sometimes this rule makes > my life a bit too hard, specially > when I just want to quickly test some ideas, like here: logistic expects a > Floating a but if I don't make things > explicit, ghc was finding its way around my use of Num a and this Floating > requirement of the exp function. > > I'll keep this rule in mind. > > Thanks a lot!! > > Regards, > MA > PD: Forgot to reply to the list before... > > Cheers Moritz >> >> [1] https://www.haskell.org/onlinereport/decls.html#sect4.5.5 >> > >

1 1

Summer of Haskell Mentors
by Edward Kmett 10 May '16

10 May '16

If you are interesting in helping out as a possible mentor for this year's Summer of Haskell, please email me, and include MENTOR in the title. Thank you! -Edward

1 0

origin of my fibonacci test
by Michael Litchard 10 May '16

10 May '16

I have some code that checks to see if a number is a fibonacci number. It's not mine, I got it from somewhere and I need to credit it. I am pretty sure I got it from Stack Exchange but my search for it went nowhere. If this looks familiar to you, or you can tell me better ways to search, please let me know. isFib :: Integer -> Bool isFib n = n == a where (_, a, _) = unFib (1, 1) n unFib :: (Integer, Integer) -> Integer -> (Integer,Integer,Integer) unFib (a, b) n | n < a = (0, 0, 1) | n < e = (2*k, c, d) | otherwise = (2*k + 1, e, f) where (k, c, d) = unFib (fibPlus (a, b) (a, b)) n (e, f) = fibPlus (a, b) (c, d) fibPlus :: (Integer, Integer) -> (Integer, Integer) -> (Integer,Integer) fibPlus (a, b) (c, d) = (bd - (b - a)*(d - c), a*c + bd) where bd = b*d

3 3

Myrtle Software is looking for Haskell developers for exciting graphics/compilers/hardware work
by Joe Hermaszewski 09 May '16

09 May '16

https://www.myrtlesoftware.com/vacancies/ We're a small software company in Cambridge, UK. We are working on some cool tech for lowering image processing algorithms to efficient hardware designs with a focus on putting these in autonomous vehicles. Our compiler is written completely in Haskell as well as some other tools we've written in house. We are looking to hire some more Haskell talent to help drive things forward. Please ask if you have any questions!

1 0

Re: [Haskell-cafe] Problems with function recursion in Haskell
by Johannes Waldmann 09 May '16

09 May '16

> ... homework ... it is highly unlikely that you will > find any help in the list or on stackoverflow. Quite often students do find homework "help" on stackoverflow. Of course SO will do nothing to discourage that. I'm not saying they should delete homework questions outright, but if they'd want quality, they'd introduce a "homework" tag so that these questions can be avoided more easily by people who would want to use SO to read/write quality answers/questions. But it seems that SO's goal is mostly numbers, that is, users. Actually, viewers for the job ads. And as long as the advertisers are paying ... Anyway, back to Haskell (but not leaving rant mode): the code example in the original question, although being rather short, manages to showcase several features that should be avoided in introductory teaching: numbers, lists, strings, and IO. (*) But, perhaps the instructor had a specific motivation. We can only guess, and that is why the recommended way for getting help with homework is (in that order): pay attention in class, then work on the exercises on your own, then with fellow students, and with the remaining questions, go to your instructor. - J.W. (*) and, recently, we should also avoid tuples https://mail.haskell.org/pipermail/libraries/2016-February/026678.html (I like the "matlab league" characterisation)

1 0

WST 2016 - First Call for Papers
by Salvador Lucas 09 May '16

09 May '16

========================================================================== WST 2016 - 1st Call for Papers 15th International Workshop on Termination September 5-7, 2016, Obergurgl, Austria http://cl-informatik.uibk.ac.at/events/wst-2016/ ========================================================================== The Workshop on Termination (WST) traditionally brings together, in an informal setting, researchers interested in all aspects of termination, whether this interest be practical or theoretical, primary or derived. The workshop also provides a ground for cross-fertilization of ideas from term rewriting and from the different programming language communities. The friendly atmosphere enables fruitful exchanges leading to joint research and subsequent publications. The event is held as part of CLA 2016 http://cl-informatik.uibk.ac.at/events/cla-2016/ IMPORTANT DATES: * submission June 22, 2016 * notification July 12, 2016 * final version August 3, 2016 * workshop September 5-7, 2016 TOPICS: The 15th International Workshop on Termination welcomes contributions on all aspects of termination and termination analysis. Contributions from the imperative, constraint, functional, and logic programming communities, and papers investigating applications of complexity or termination (for example in program transformation or theorem proving) are particularly welcome. Topics of interest include all aspects of termination. This includes (but is not limited to): * certification of termination and complexity proofs * challenging termination problems * comparison and classification of termination methods * complexity analysis in any domain * implementation of termination and complexity methods * implicit computational complexity * infinitary normalization * non-termination analysis and loop detection * normalization in lambda calculi * operational termination of conditional rewrite systems * ordinal notation and subrecursive hierarchies * SAT, SMT, and constraint solving for (non-)termination analysis * scalability and modularity of termination methods * termination analysis in any domain * well-founded relations and well-quasi-orders COMPETITION: There will be a live complexity and termination competition during the workshop, including time to present both the results and the tools of the participants. More details will be provided in a dedicated announcement on the competition. PROGRAM COMMITTEE: * Ugo Dal Lago Bologna University * Jörg Endrullis VU University Amsterdam * Yukiyoshi Kameyama University of Tsukuba * Salvador Lucas Universidad Politécnica de Valencia * Aart Middeldorp University of Innsbruck, co-chair * Andrey Rybalchenko Microsoft Research * Thomas Ströder RWTH Aachen * René Thiemann University of Innsbruck, co-chair * Andreas Weiermann Ghent University INVITED SPEAKERS: * Rainer Hähnle TU Darmstadt SUBMISSION: Submissions are short papers/extended abstract which should not exceed 5 pages. There will be no formal reviewing. In particular, we welcome short versions of recently published articles and papers submitted elsewhere. The program committee checks relevance and provides additional feedback for each submission. The accepted papers will be made available electronically before the workshop. Papers should be submitted electronically via the submission page: http://www.easychair.org/conferences/?conf=wst2016 Final versions should be created using LaTeX and the LIPIcs style file http://drops.dagstuhl.de/styles/lipics/lipics-authors.tgz

1 0

Automatic differentiation (AD) with respect to list of matrices in Haskell
by Miguel A. Santos 08 May '16

08 May '16

I am trying to understand how can I use Numeric.AD (automatic differentiation) in Haskell. I defined a simple matrix type and a scalar function taking an array and two matrices as arguments. I want to use AD to get the gradient of the scoring function with respect to both matrices, but I'm running into compilation problems. Here is the code: ------------------------------- {-# LANGUAGE DeriveTraversable, DeriveFunctor, DeriveFoldable #-}import Numeric.AD.Mode.Reverse as Rimport Data.Traversable as Timport Data.Foldable as F --- Non-linear function on "vectors" logistic x = 1.0 / (1.0 + exp(-x) ) phi v = map logistic v phi' (x:xs) = x : (phi xs) --- dot product dot u v = foldr (+) 0 $ zipWith (*) u v --- simple matrix typedata Matrix a = M [[a]] deriving (Eq,Show,Functor,F.Foldable,T.Traversable) --- action of a matrix on a vector mv _ [] = [] mv (M []) _ = [] mv ( M m ) v = ( dot (head m) v ) : (mv (M (tail m)) v ) --- two matrices mbW1 = M $ [[1,0,0],[-1,5,1],[1,2,-3]] mbW2 = M $ [[0,0,0],[1,3,-1],[-2,4,6]] --- two different scoring functions sc1 v m = foldr (+) 0 $ (phi' . (mv m) ) v sc2 :: Floating a => [a] -> [Matrix a] -> a sc2 v [m1, m2] = foldr (+) 0 $ (phi' . (mv m2) . phi' . (mv m1) ) v strToInt = read :: String -> Double strLToIntL = map strToInt--- testing main = do putStrLn $ "mbW1:" ++ (show mbW1) putStrLn $ "mbW2:" ++ (show mbW2) rawInput <- readFile "/dev/stdin" let xin= strLToIntL $ lines rawInput putStrLn "sc xin mbW1" print $ sc1 xin mbW1 --- ok. = putStrLn "grad (sc1 xin) mbW1" print $ grad ( sc1 xin) mbW1 -- yields an error: expects xin [Reverse s Double] instead of [Double] putStrLn "grad (sc1 [3,5,7]) mbW1" print $ grad ( sc1 [3,5,7]) mbW1 --- ok. = putStrLn "sc2 xin [mbW1,mbW2]" print $ sc2 xin [mbW1, mbW2] putStrLn "grad (sc2 [3,5,7) [mbW1,mbW2]" print $ grad ( sc2 [3,5,7]) [mbW1, mbW2] --- Error: see text -------------------------------- The last line (grad on sc2) gives the following error: --------------------------------- Couldn't match type ‘Reverse s (Matrix Double)’ with ‘Matrix (Reverse s (Matrix Double))’ Expected type: [Reverse s (Matrix Double)] -> Reverse s (Matrix Double) Actual type: [Matrix (Reverse s (Matrix Double))] -> Reverse s (Matrix Double) In the first argument of ‘grad’, namely ‘(sc2 [3, 5, 7])’ In the second argument of ‘($)’, namely ‘grad (sc2 [3, 5, 7]) [mbW1, mbW2]’ --------------------------------- I don't understand where the "Matrix of Matrix" in the actual type seen comes from. I'm feeding the grad with a curried version of sc2, making it a function on a list of Matrix. Commenting out the two offending lines runs without problem, i.e., the first gradient works and is correctly calculated (I'm feeding [1,2,3] as input to the program): ------------------- mbW1:M [[1.0,0.0,0.0],[-1.0,5.0,1.0],[1.0,2.0,-3.0]] mbW2:M [[0.0,0.0,0.0],[1.0,3.0,-1.0],[-2.0,4.0,6.0]] sc1 xin mbW11232.0179800657874893 grad (sc1 [3,5,7]) mbW1 M [[3.0,5.0,7.0],[7.630996942126885e-13,1.2718328236878141e-12,1.7805659531629398e-12],[1.0057130122694228e-3,1.6761883537823711e-3,2.3466636952953197e-3]] sc2 xin [mbW1,mbW2]1.8733609463863194 ------------------- Both errors are an issue. I want to take the gradient of any such sc2 scoring function, depending on an array of matrices, evaluated at any given "point" xin. Clearly, I'm not yet understanding the AD library well enough. Any help would be appreciated. -- Public key ID: E8FE60D7 Public key server: see, e.g., hkp://keys.gnupg.net

2 1

Could Haddock export documentation with type family applications normalised?
by Oliver Charles 08 May '16

08 May '16

Hi all, I'm working on a library that uses quite a lot of type "magic" (as some would call it), but really it's all just implementation details. The type families are necessary for me to write the code, but an outside understanding of these type families shouldn't be necessary to understand the library. Unfortunately, Haddock does not align with that goal. To give you a feeling for things, take the following types: data Expr (t :: k) data AsHaskell (t :: k) data BaseType = DBInt | DBText type family Col (f :: k -> *) (a :: k) :: * type instance Col Expr (a :: BaseType) = Expr a type instance Col AsHaskell (a :: BaseType) = BaseTypeAsHaskell a type family BaseTypeAsHaskell (bt :: BaseType) :: * where BaseTypeAsHaskell 'DBInt = Int BaseTypeAsHaskell 'DBText = String class Lit (exprType :: k) where lit :: Col AsHaskell exprType -> Expr exprType instance Lit 'DBInt where lit = ... instance Lit 'DBText where lit = ... (I am modelling the interaction with remote relational databases, to provide a little more context) Now when I export this, I end up with the following: Fine, not much needs to change there. Haddock now also gives me specialised types for instances, but these don't go far enough: Instances Lit BaseType DBInt Methods lit :: Col (TYPE Lifted) DBInt (AsHaskell DBInt) exprType -> Expr DBInt exprType But this is considerably less helpful: First, it seems to be broken, as it mentions the exprType variable, when is just DBint. Secondly, it mentions all sorts of kinds which are, in my opinion, unreadable in the current form. All of these problems would be solved if we just normalised this type family application as far as possible. What I *really* want to export is: Instances Lit DBInt Methods lit :: Int -> Expr DBInt This is the type I want my users to be aware of. Has this been discussed before? If not, how do people feel about this? Ollie

2 2

Storing big datasets
by Mikhail Volkhov 08 May '16

08 May '16

Hi! I'm using ACID package as main database -- it's simple and... ACID (which is cool of course). So now I need to store up to ~30GB of data in a single data structure (!) that will be constantly updated (some kind of a huge tree set). Here's a question -- how to operate that big structure? 1. It doesn't even fit in RAM 2. It should be updated atomically and frequently (every 10 seconds up to 500 elements out of 10^7). 3. What structures should I use? I'd like to store up to 10^6~10^7 some simple elements there too, that will be gigabytes of data. So it seems to me I can't use Data.Set. Thanks for any ideas! -- Volkhov Mikhail M3#38 ITMO study group 17' Computer Technologies Department

6 13