November 2017 - Haskell-Cafe

Re: [Haskell-cafe] [ANN]: fin & vec
by Oleg Grenrus 21 Nov '17

21 Nov '17

Thanks for more references! I was quite sure I didn't found all packages around fin/nat/vec (and I feel a little bad for making "standards" problem worse :) - https://hackage.haskell.org/package/finite-typelits uses GHC.TypeLits.Nat (fair thing to do). - https://hackage.haskell.org/package/vector-sized builds on top of that and looks like a nice package too! I dislike GHC.TypeLits.Nat for doing induction over, yet for many things they (+ [1,2] or [3]) are great. I have to write that down in the description of the package(s). Hopefully the approaches: compiler built-in magic and DataKinds definition would be unified in the future. Cheers, Oleg. - [1] https://hackage.haskell.org/package/ghc-typelits-natnormalise - [2] https://hackage.haskell.org/package/ghc-typelits-extra - [3] http://hackage.haskell.org/package/constraints-0.9.1/docs/Data-Constraint-N… On 21.11.2017 15:20, Alexey Vagarenko wrote: > I wrote a package not long ago which also uses static inlining for > similar things: https://hackage.haskell.org/package/static-tensor > > There is also https://hackage.haskell.org/package/vector-sized which > is a wrapper around 'vector' library. > > <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_cam…> > Virus-free. www.avg.com > <http://www.avg.com/email-signature?utm_medium=email&utm_source=link&utm_cam…> > > > > 2017-11-21 17:27 GMT+05:00 Oleg Grenrus <oleg.grenrus(a)iki.fi > <mailto:oleg.grenrus@iki.fi>>: > > I'm happy to announce two packages: > > - http://hackage.haskell.org/package/fin > <http://hackage.haskell.org/package/fin> > - http://hackage.haskell.org/package/vec > <http://hackage.haskell.org/package/vec> > > In short they provide following types: > > data Nat where Z | S Nat > > data Fin (n :: Nat) where > Z :: Fin ('S n) > S :: Fin n -> Fin ('S n) > > data Vec (n :: Nat) a where > VNil :: Vec 'Z a > (:::) :: a -> Vec n a -> Vec ('S n) a > > Main motivation for creating these packages is that I didn't found > anything > similar on Hackage. Before comparison with the alternatives, let me > mention few > highlights: > > - `fin` and `vec` support GHC-7.8.4 .. GHC-8.2.1; and I plan to > keep support > window as wide as possible. > > - `fin` package provides `Data.Fin.Enum` module to work > generically with > enumerations. It's (subjectively) more ergonomic than working with > `All ((:~:) a) xs => NS I xs` from `generics-sop` [1] > > - `fin` package defines `InlineInduction` class, > letting us trick GHC to unfold recursion. One general example is > > unfoldedFix :: forall n a proxy. InlineInduction n > => proxy n -> (a -> a) -> a > unfoldedFix _ = getFix (inlineInduction1 start step :: Fix > n a) > where > start :: Fix 'Z a > start = Fix fix > > step :: Fix m a -> Fix ('S m) a > step (Fix go) = Fix $ \f -> f (go f) > > newtype Fix (n :: Nat) a = Fix { getFix :: (a -> a) -> a } > > So, for statically known @n@, GHC's inliner will "simplify": > > unfoldedFix (Proxy :: Proxy Nat3) f = f (f (f (fix f))) > > - `fin` has very light dependency footprint: > `base`, `deepseq`, `hashable` (and transitively `text`) on GHC>=8.0 > > - `vec` has a little more dependencies, essentially `lens`. See > dependency > diagram in the readme. [2] > > - `vec` comes in three flavours: > > * __naive__: with explicit recursion. It's simple, > constraint-less, > yet slow. > > * __pull__: using `Fin n -> a` representation, which fuses well, > but makes some programs hard to write. And > > * __inline__: which uses `InlineInduction`, unrolling > recursion if the size of 'Vec' is known statically. > > Differences with other packages > ------------------------------- > > ### fin > > - [type-natural](http://hackage.haskell.org/package/type-natural > <http://hackage.haskell.org/package/type-natural>) depends > on @singletons@ package. `fin` will try to stay light on the > dependencies, > and support as many GHC versions as practical. > > - [peano](http://hackage.haskell.org/package/peano > <http://hackage.haskell.org/package/peano>) is very incomplete > > - [nat](http://hackage.haskell.org/package/nat > <http://hackage.haskell.org/package/nat>) as well. > > - > [PeanoWitnesses](https://hackage.haskell.org/package/PeanoWitnesses > <https://hackage.haskell.org/package/PeanoWitnesses>) > doesn't use @DataKinds@. > > - > [type-combinators](http://hackage.haskell.org/package/type-combinators > <http://hackage.haskell.org/package/type-combinators>) > is a big package. > > ### vec > > - [linear](http://hackage.haskell.org/package/linear > <http://hackage.haskell.org/package/linear>) has 'V' type, > which uses 'Vector' from @vector@ package as backing store. > `Vec` is a real GADT, but tries to provide as many useful > instances (upto > @lens@). > > - [sized-vector](http://hackage.haskell.org/package/sized-vector > <http://hackage.haskell.org/package/sized-vector>) depends > on 'singletons' package. `vec` isn't light on dependencies either, > but try to provide wide GHC support. > > - [sized](https://hackage.haskell.org/package/sized > <https://hackage.haskell.org/package/sized>) also depends > on a 'singletons' package. The 'Sized f n a' type is > generalisation of > linears 'V' for any 'ListLike'. > > - > [clash-prelude](https://hackage.haskell.org/package/clash-prelude > <https://hackage.haskell.org/package/clash-prelude>) > is a kitchen sink package, which has 'CLaSH.Sized.Vector' module. > Also depends on 'singletons'. > > Disclaimer > ---------- > > These are the "first released versions", i.e. `fin-0` and `vec-0`. > Don't be fooled by 0, we use them in production. > > We don't have (yet?) a use-case where proper full inlining would > matter, it > seems to work with simple examples. The `vec` package includes > simple dot > product benchmark, it gives sensible results: > > - *list* version sets the baseline, built-in fusion seems to kick in. > - using `vector` is 3x slower (?) > - naive `Vec` is even slower, not surprisingly > - `Data.Vec.Pull` approach is slower, *except* > - that without conversions it's up to speed with `vector` > - `InlineInduction` is *fastest*. > > Acknowledgements > ---------------- > > - *APLicative Programming with Naperian Functors* [3] has the very > similar > `Nat`, `Fin` and `Vec` (sections 2--4). I spotted few missing > functions in > `vec` by re-reading the paper (`vgroup` is `chunks` and `viota` is > `universe`). > I don't claim that my library is novel in any kind :) > - I learned *Pull array* idea from Josef Svenningsson talk at SmallFP > 2017 [4]. > See the video [5] if interested. > - Herbert Valerio Riedel for the idea to split `fin` out of `vec`. > It turned > out to be very light package. > - Andres Löh for discussions about `generics-sop` [1], and about > the static > inlining idea. > - Joachim Breitner for creating `inspection-testing` [6], which > really helps > validating optimisations working. > > Cheers, > Oleg > > > - [1] http://hackage.haskell.org/package/generics-sop > <http://hackage.haskell.org/package/generics-sop> > - [2] https://github.com/phadej/vec#dependencies > <https://github.com/phadej/vec#dependencies> > - [3] > https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/aplicative.pdf > <https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/aplicative.pdf> > - [4] http://clojutre.org/2017/ > - [5] > https://www.youtube.com/watch?v=5PZh0BcjIbY&list=PLetHPRQvX4a9uUK2JUZrgjtC_… > <https://www.youtube.com/watch?v=5PZh0BcjIbY&list=PLetHPRQvX4a9uUK2JUZrgjtC_…> > - [6] http://hackage.haskell.org/package/inspection-testing > <http://hackage.haskell.org/package/inspection-testing> > > > > _______________________________________________ > Haskell-Cafe mailing list > To (un)subscribe, modify options or view archives go to: > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > <http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe> > Only members subscribed via the mailman list are allowed to post. > >

2 1

[ANN]: fin & vec
by Oleg Grenrus 21 Nov '17

21 Nov '17

I'm happy to announce two packages: - http://hackage.haskell.org/package/fin - http://hackage.haskell.org/package/vec In short they provide following types: data Nat where Z | S Nat data Fin (n :: Nat) where Z :: Fin ('S n) S :: Fin n -> Fin ('S n) data Vec (n :: Nat) a where VNil :: Vec 'Z a (:::) :: a -> Vec n a -> Vec ('S n) a Main motivation for creating these packages is that I didn't found anything similar on Hackage. Before comparison with the alternatives, let me mention few highlights: - `fin` and `vec` support GHC-7.8.4 .. GHC-8.2.1; and I plan to keep support window as wide as possible. - `fin` package provides `Data.Fin.Enum` module to work generically with enumerations. It's (subjectively) more ergonomic than working with `All ((:~:) a) xs => NS I xs` from `generics-sop` [1] - `fin` package defines `InlineInduction` class, letting us trick GHC to unfold recursion. One general example is unfoldedFix :: forall n a proxy. InlineInduction n => proxy n -> (a -> a) -> a unfoldedFix _ = getFix (inlineInduction1 start step :: Fix n a) where start :: Fix 'Z a start = Fix fix step :: Fix m a -> Fix ('S m) a step (Fix go) = Fix $ \f -> f (go f) newtype Fix (n :: Nat) a = Fix { getFix :: (a -> a) -> a } So, for statically known @n@, GHC's inliner will "simplify": unfoldedFix (Proxy :: Proxy Nat3) f = f (f (f (fix f))) - `fin` has very light dependency footprint: `base`, `deepseq`, `hashable` (and transitively `text`) on GHC>=8.0 - `vec` has a little more dependencies, essentially `lens`. See dependency diagram in the readme. [2] - `vec` comes in three flavours: * __naive__: with explicit recursion. It's simple, constraint-less, yet slow. * __pull__: using `Fin n -> a` representation, which fuses well, but makes some programs hard to write. And * __inline__: which uses `InlineInduction`, unrolling recursion if the size of 'Vec' is known statically. Differences with other packages ------------------------------- ### fin - [type-natural](http://hackage.haskell.org/package/type-natural) depends on @singletons@ package. `fin` will try to stay light on the dependencies, and support as many GHC versions as practical. - [peano](http://hackage.haskell.org/package/peano) is very incomplete - [nat](http://hackage.haskell.org/package/nat) as well. - [PeanoWitnesses](https://hackage.haskell.org/package/PeanoWitnesses) doesn't use @DataKinds@. - [type-combinators](http://hackage.haskell.org/package/type-combinators) is a big package. ### vec - [linear](http://hackage.haskell.org/package/linear) has 'V' type, which uses 'Vector' from @vector@ package as backing store. `Vec` is a real GADT, but tries to provide as many useful instances (upto @lens@). - [sized-vector](http://hackage.haskell.org/package/sized-vector) depends on 'singletons' package. `vec` isn't light on dependencies either, but try to provide wide GHC support. - [sized](https://hackage.haskell.org/package/sized) also depends on a 'singletons' package. The 'Sized f n a' type is generalisation of linears 'V' for any 'ListLike'. - [clash-prelude](https://hackage.haskell.org/package/clash-prelude) is a kitchen sink package, which has 'CLaSH.Sized.Vector' module. Also depends on 'singletons'. Disclaimer ---------- These are the "first released versions", i.e. `fin-0` and `vec-0`. Don't be fooled by 0, we use them in production. We don't have (yet?) a use-case where proper full inlining would matter, it seems to work with simple examples. The `vec` package includes simple dot product benchmark, it gives sensible results: - *list* version sets the baseline, built-in fusion seems to kick in. - using `vector` is 3x slower (?) - naive `Vec` is even slower, not surprisingly - `Data.Vec.Pull` approach is slower, *except* - that without conversions it's up to speed with `vector` - `InlineInduction` is *fastest*. Acknowledgements ---------------- - *APLicative Programming with Naperian Functors* [3] has the very similar `Nat`, `Fin` and `Vec` (sections 2--4). I spotted few missing functions in `vec` by re-reading the paper (`vgroup` is `chunks` and `viota` is `universe`). I don't claim that my library is novel in any kind :) - I learned *Pull array* idea from Josef Svenningsson talk at SmallFP 2017 [4]. See the video [5] if interested. - Herbert Valerio Riedel for the idea to split `fin` out of `vec`. It turned out to be very light package. - Andres Löh for discussions about `generics-sop` [1], and about the static inlining idea. - Joachim Breitner for creating `inspection-testing` [6], which really helps validating optimisations working. Cheers, Oleg - [1] http://hackage.haskell.org/package/generics-sop - [2] https://github.com/phadej/vec#dependencies - [3] https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/aplicative.pdf - [4] http://clojutre.org/2017/ - [5] https://www.youtube.com/watch?v=5PZh0BcjIbY&list=PLetHPRQvX4a9uUK2JUZrgjtC_… - [6] http://hackage.haskell.org/package/inspection-testing

2 1

problem with compiler error message
by Dmitry Olshansky 21 Nov '17

21 Nov '17

Hello cafe! It seems that this behavior is wrong: > class Foo a where { type Bar a; baz :: a -> Bar a } > baz zzz -- zzz is not in scope <interactive>:17:1: error: • Couldn't match expected type ‘Bar a’ with actual type ‘Bar a0’ NB: ‘Bar’ is a type function, and may not be injective The type variable ‘a0’ is ambiguous • In the ambiguity check for the inferred type for ‘it’ To defer the ambiguity check to use sites, enable AllowAmbiguousTypes When checking the inferred type it :: forall a. Bar a As opposite - correct behavior: > :t negate negate :: Num a => a -> a > negate zzz <interactive>:19:8: error: Variable not in scope: zzz Best regards, Dmitry

2 2

Questions about Numeric.AD / Automatic differentiation
by Sean Matthews 21 Nov '17

21 Nov '17

I'm having some problems with Numeric.AD (translation, things are not working for reason that I don't understand). Note I don't have much experience with this package, so these are newbie questions, thus appropriate answers may involve pointing me to a document somewhere out there on the net. Anyway, here is my problem: I have a function (call it f x theta) which I have defined purely in terms of basic arithmetic functions (+/-/(/)/*/**) glued together using standard applicative functor operations has type f :: m1 (m2 Double) -> m3 Double -> Double f x theta = ... m1 m2 and m3 are all Traversable. f is defined purely in terms of basic arithmetic operations, (+/-/(/)/*/**) glued together using standard applicative functor operations, and m1 m2 and m3 are all pretty trivial record types (no recursion, even). I would like to write df x theta = grad (f x) theta But it refuses to type, even though (admittedly quite a lot) simpler versions do. So what am I missing? Does AD not go through Applicative? That seems unlikely to me. Any advice / suggestions, etc. gratefully received. Sean Matthews -- Sean Matthews seanmatthews1(a)gmail.com / +49 1515 800 1901

2 2

argument counts...
by Gregory Guthrie 20 Nov '17

20 Nov '17

I have a simple function: revFn (x:xs) = (revFn xs) . (x:) Of course GHCi correctly infers the type as: revFn :: [a] -> [a] -> c Adding the base case: revFn [] xs = xs Now gives an error; "Equations for 'revF' have different numbers of arguments" Of course this can be "fixed" by either adding the cancelled argument to the first clause, or converting the base case to only have one explicit argument, and a RHS of a lambda or identity function. But since the interpreter already correctly inferred that the first clause has two arguments (with only one explicit), why does it then ignore this and give an error when the second clause shows two explicit arguments? The types are all correct in either case - why require explicit arguments? Or, perhaps I am missing something simple?

5 4

Re: [Haskell-cafe] Speculation, OT: Program a Spreadsheet
by Olaf Klinke 20 Nov '17

20 Nov '17

Hello Trent, let me suggest to step back and think about why people use spreadsheets. They provide access to data analysis functions, statistics and graphing that is otherwise missing (at least on) Windows systems. Serious number crunching is not done in spreadsheets, though. There is R, Matlab and the like. You should not try to comptete with that. The big selling point (in my eyes) of spreadsheets over scripting languages like R is that the data as well as the formulae and intermediate results are, well, spread out in front of your eyes. That is e.g. desirable when you need someone else to understand what you did and how you arrived at the answer given. But is it important that the intermediate result resides in cells C2 to C13? Certainly not. I wrote a small financial application in Haskell that would otherwise be done in spreadsheets. Haskell provided, via its type system, extra sanity checks and much more that spreadsheets don't provide. However, I often wished that there was a way to disassemble the computation into logical bits that can be formatted neatly and be presented to a human inspector. Haskell provides ways to do this, e.g. by mixing Haskell and LaTeX, or writing a small DSL with two interpreters, one for calculations, one for layout. So instead of enhancing a spreadsheet format I'd rather have a scripting language with a workbook file format à la Mathematica, where comments, code and results of computations are displayed together. Changing a formula triggers change in the results. (The workbooks I've seen don't do that.) Input data and intermediate results can be hidden or expanded via mouse click. Results can be traced back through the workbook's formulae up to the input data. (The latter is not always easy in spreadsheets.) One would need to research whether such a language exists. If not, I'd be happy to help develop it. Olaf

5 5

Re: [Haskell-cafe] Speculation, OT: Program a Spreadsheet
by dominic＠steinitz.org 20 Nov '17

20 Nov '17

Here’s a presentation about a functional language embedded in Excel which I used when I worked at an investment bank https://www.youtube.com/watch?v=uICBMTeIl2U http://cufp.org/2009/fmd-functional-development-excel.html As far as I know the code is still in use (I recall there was something like 400 users in the bank) and was never open-sourced but it may provide some ideas given it was pretty successful internally. Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

1 0

implement a simple DSL meet problem with env data can't be changed
by mo jia 19 Nov '17

19 Nov '17

Base on the correct compiler desc on https://github.com/pa-ba/calc-comp Here is the source code module Lambda_define ( Name, Expr, eval )where import Prelude hiding (null, lookup, map, filter) import Data.HashMap.Lazy type Name = [Char] data Expr = Val Int | Add [Expr] | Var Name | Abs Name Expr | App Expr Expr | Define Name Expr | Begin [Expr] | Let (Name, Expr) Expr data Env = Root | Env { current :: HashMap Name Value, parent :: Env } data Value = Num Int | Clo Name Expr Env envLookup :: Name -> Env -> Value envLookup n Root = Num 10000 --- fix it envLookup n env = case lookup n (current env) of Just v -> v otherwise -> envLookup n (parent env) --------------- setvar :: Name -> Value -> Env -> Env setvar n v Root = Env{current=fromList [(n, v)] , parent=Root } setvar n v Env{current=c, parent=p} = Env{current=(insert n v c), parent=p } eval :: Expr -> Env -> (Value, Env) eval (Val n) e = (Num n , e) eval (Add [x , y]) e = case eval x e of (Num n, e') -> case eval y e of (Num m, e1') -> (Num (n+m), e) eval (Add [x]) e = case eval x e of (Num n, e') -> (Clo "y" (Add [(Val n), (Var "y")]) e' , e) eval (Var n) e = (envLookup n e, e) eval (Abs n x) e = (Clo n x e, e) eval (App x y) e = case eval x e of (Clo n' x' e', env') -> case eval y e of (vy, e'') -> (fst (eval x' (Env (fromList [(n', vy)]) e')), e ) --- the saved clojure env can't be changed eval (Define n e) env = case eval e env of (v, e') -> (Num 0, setvar n v env) --- fix me why 0 eval (Let (n, e1) e2) env = ------ Let should don't chanve the env (fst (eval e2 (Env (fromList [(n, (fst (eval e1 env)))]) env)), env) eval (Begin xs) e = case length xs of 0 -> (Num 0, Root) -- never come here 1 -> case eval (xs !! 0) e of (v, e') -> (v, e') n -> case eval (Begin (take (n - 1) xs)) e of (v, e') -> eval (last xs) e' test1 = eval (Begin [(Define "z" (Val 1)), (Define "y" (Abs "x" (Add [(Var "z"), (Var "x")]))), (Define "x" (Val 7)), (Define "z" (Val 90)), (Add [(Val 5), (App (Var "y") (Val 8))])]) Root test2 = eval (Begin [(Define "z" (Val 1)), (Define "y" (Abs "x" (Add [(Var "z"), (Var "x")]))), (Define "x" (Val 7)), (Let ("z", (Val 90)) (Add [(Val 5), (App (Var "y") (Val 8))])) ]) Root In case you want to see the total program. I put it into https://github.com/jiamo/correct_compiler/blob/master/src/Lambda_define.hs Here is my problem: I want test1 return (Num 103) I want test2 return (Num 14) But now it both return (Num 14) One problem I can figure out that "the eval of Define return a new env can't change the old env" Any one have suggests?

1 0

latin file encoding
by Henning Thielemann 17 Nov '17

17 Nov '17

I have a LATIN-1 encoded file on a UTF-8 configured system: $ iconv -f latin1 Text Häßkell $ echo $LANG de_DE.UTF-8 Thus, a Haskell program cannot process it as it is: $ cat Text | ghc-8.2.2 -e 'interact id' | iconv -f latin1 <interactive>: <stdin>: hGetContents: invalid argument (invalid byte sequence) So far, so expected. Now I want to run it with latin encoding: $ cat Text | (LANG=de_DE ghc-8.2.2 -e 'interact id') | iconv -f latin1 <interactive>: <stdin>: hGetContents: invalid argument (invalid byte sequence) That's unexpected. Is this the reason: $ LANG=de_DE ghc-8.2.2 -e 'print System.IO.localeEncoding' ASCII ? Btw. what would be the Locale name for Latin-1 encoding?

1 1

2017 state of Haskell survey results
by Taylor Fausak 16 Nov '17

16 Nov '17

I am excited to announce that the results of the 2017 state of Haskell survey are now available: http://taylor.fausak.me/2017/11/15/2017-state-of-haskell-survey-results/ <http://taylor.fausak.me/2017/11/15/2017-state-of-haskell-survey-results/> Thanks to everyone who responded!

1 0