sdiehl / write-you-a-haskell Goto Github PK

This project is great. Is there any say I can show my gratitude (such as gratipay.com).

I'm not sure if it is a feature or an implementation artefact, but the user can find it with :browse and using it leads to trouble:

Poly> 1
1 : Int
Poly> :browse
it : Int
Poly> it+it
4 : Int
Poly> it==it
poly: Pattern match failure in do expression at Eval.hs:39:5-11

In the REPL section of the Parsers section, there's a rather strange sentence (to me at least):

When the user pressed enters a EOF or sends a SIGQUIT to input, getInputLine will yield Nothing and can handle the exit logic.

I believe the first part, "the user pressed enters a EOF", needs some tweaking.

Hi, I've just manually converted the pdf into Ebook + AZW3 formats.

It's not using the script but there seemed to be interest to these formats so wondered if I should make adjustments to the menu and add 2 extra links?
but I assume you wouldn't want the file living on the repo as they are about 3mb in total! 🤔

Here is a zip of them both

edit: the Epub version was the wrong one! (reuploaded)

Write you a haskell Ebook AZW3.zip

MacOS Catalina 10.15.5, GHC-8.8.3, Stack-2.3.1, current LaTeX (MacTeX-2020):

$ stack exec make
pandoc -c css/style.css --filter includes.hs --template template.html -s -f markdown -t html --standalone --toc --toc-depth=2 --mathjax="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" --highlight-style pygments -o 000_introduction.html 000_introduction.md

includes.hs:6:1: error:
    Could not find module ‘Text.Pandoc’
    Perhaps you meant Text.Parsec (from parsec-3.1.14.0)
    Use -v (or `:set -v` in ghci) to see a list of the files searched for.
  |
6 | import Text.Pandoc
  | ^^^^^^^^^^^^^^^^^^

includes.hs:10:1: error:
    Could not find module ‘Text.Pandoc.JSON’
    Use -v (or `:set -v` in ghci) to see a list of the files searched for.
   |
10 | import Text.Pandoc.JSON
   | ^^^^^^^^^^^^^^^^^^^^^^^

includes.hs:11:1: error:
    Could not find module ‘Text.Pandoc.Walk’
    Use -v (or `:set -v` in ghci) to see a list of the files searched for.
   |
11 | import Text.Pandoc.Walk
   | ^^^^^^^^^^^^^^^^^^^^^^^
Error running filter includes.hs:
Filter returned error status 1
make: *** [000_introduction.html] Error 83

$ stack --version
Version 2.3.1, Git revision de2a7b694f07de7e6cf17f8c92338c16286b2878 (8103 commits) x86_64 hpack-0.33.0
$ pandoc --version
pandoc 2.9.2.1
Compiled with pandoc-types 1.20, texmath 0.12.0.2, skylighting 0.8.4
Default user data directory: /Users/ur20980/.local/share/pandoc or /Users/ur20980/.pandoc
Copyright (C) 2006-2020 John MacFarlane
Web:  https://pandoc.org
This is free software; see the source for copying conditions.
There is no warranty, not even for merchantability or fitness
for a particular purpose.
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.8.3

It would be great if you could help getting this book compiled/built. Thanks!

The data types given for the example abstract syntax:

type Name = String

data Expr
  = Var Name
  | Lit Name
  | Op PrimOp [Expr]
  | Let Name [Name] Expr

data Lit 
  = LitInt Int

does not match the value given later:

Let "f" ["x"] (Op Add [Var "x", Lit (LitInt 1)])

Specifically Lit (LitInt 1).

Stephen, wonderful work here!

The Untyped chapter includes a section on pretty printing but some of the material relating to pretty printing appears earlier, at the end of the Reduction section, and seems out of order.

When attempting to run the type checker on the example given in the repo with factorial, I run into a typechecker error:

Poly> let fact = fix (\fact -> \n -> if (n == 0) then 1 else  ( n * ( fact (n-1) ) )    )
Cannot unify types:
	Int
with
	Int -> d

According to the book this should spit out the correct type.

The Substitutable instance for Type is currently defined as follows:

instance Substitutable Type where
  apply _ (TCon a)       = TCon a
  apply s t@(TVar a)     = Map.findWithDefault t a s
  apply s (t1 `TArr` t2) = apply s t1 `TArr` apply s t2

I believe the TVar case is incomplete. Consider the following substitution:

x <- y
y <- Int

If we apply this substitution to type variable x, we obtain y, when we should obtain Int. I think this case should instead recursively apply the substitution to the type found in the map.

I think #90 from @jeffreyrosenbluth introduced a bug. At least, I think it was that commit.

Prior to this commit (ie. using #1e609fb), you can do something like the following:

Poly> 2 + 3
5 : Int

Now, I get the following:

Poly> 2 + 3
Cannot unify types:
	Int
with
	Int -> a

Weirdly, it works for the * operator, but fails only for + and -:

I suspect there's something weird going on in the parser because:

Poly> 2 + x
"<stdin>" (line 1, column 5):
unexpected "x"
expecting digit
Poly> 2 * x
4 : Int

Paragraph 2, sentence 1 of http://dev.stephendiehl.com/fun/type_systems.html#type-systems

Thank you for your great work :-)

The following line's "λ" can be displayed in HTML, but can not be displayed correctly in PDF.
(Please ignore if my environment dependent)

• 003_lambda_calculus.md, line 358 (at pdf p.50):

  $$ \mathtt{let}\ a = e\ \mathtt{in}\ b \quad := \quad (λa.b) e $$

  maybe

  $$ \mathtt{let}\ a = e\ \mathtt{in}\ b \quad := \quad (\lambda a.b) e $$

The following lines' "λ" and "≡" can be displayed in HTML, but can not be displayed correctly in PDF.

• 005_evaluation.md, line 84 (at pdf p.69)

  (\x. \y. y x) (2 + 2) λx. x + 1

• 005_evaluation.md, line 173 (at pdf p.71)

  => (\y.y (2 + 2)) λx. x + 1

• 006_hindley_milner.md, line 1286 (at pdf p.101)

  λ: main

• 007_path.md, line 272-277 (at pdf p.109)

  λ> id (1+2)
  3
  λ> :type (>>=)
  (>>=) :: Monad m => m a -> (a -> m b) -> m b
  λ> :set -ddump-rn
  λ> :load test.fun

• 007_path.md, line 1235 (at pdf p.126)

  f <=< g ≡ \x -> g x >>= f

(Because not yet been able to environment, sorry in this way)

I have just started reading it, but noticed that there have been no new commits since October. I would absolutely love to see this book completed!

Really enjoying this, thanks for the hard work!

There's a typo in the lambda typing rule in Ch04 for the simply-typed LC. The types and the terms have been mixed up in the implication.

It reads

Γ, x : τ1 ⊢ e : τ2
-------------------
Γ ⊢ λx.τ2 : e1→e2

You probably meant

...
-------------------
Γ ⊢ λx.e : τ1→τ2

Please may the proprietary license be switched to one which respects the freedom of the readers?

The Evaluation chapter contains this sentence:

We will use the evaluation technique Ly extensively

What does this Ly refer to?

I dont think this typechecks

https://github.com/sdiehl/write-you-a-haskell/blob/master/004_type_systems.md#small-step-semantics

-- Evaluate a single step.
eval1 :: Expr -> Maybe Expr
eval1 expr = case expr of
  Succ t                    -> Succ <$> (eval1 t)
  Pred Zero                 -> Just Zero
  Pred (Succ t) | isNum t   -> Just t
  Pred t                    -> Pred <$> (eval1 t)
  IsZero Zero               -> Just Tr
  IsZero (Succ t) | isNum t -> Just Fl
  IsZero t                  -> IsZero <$> (eval1 t)
  If Tr  c _                -> Just c
  If Fl _ a                 -> Just a
  If t c a                  -> (\t' -> If t' c a) <$> eval1 t
  _                         -> Nothing

Consider following expressions:

let const = \x -> (\y -> x);
let y = \y -> (let f = \x -> if x then True else False in const (f y) y;

The accurate type of f is Bool -> Bool but forall a . a -> Bool was given by poly_constraints. The reason is that poly_constraints doesn't substitute type variables in constraints set when instantiate a type scheme with fresh variables. (i.e. there are still some constraints with a although forall a . a -> a has been instantiated by other fresh variables)

I've only recently learned sufficiently not-hand-wavy meaning of the word "powerful", which is if X is more powerful than Y then you can do some things with X that are not possible with Y.

However, it looks like I don't yet understand the meaning of the word "general". I would guess that "Applicatives are strictly less general than monads" means that there are more monads out there than applicatives, but the opposite is the case. Could you clarify?

Although a strong familiarity with monads, monad transformers ...

l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$ stack exec make epub
pandoc --filter includes.hs -f markdown --standalone --toc --toc-depth=2 --mathjax="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" --highlight-style pygments --epub-cover-image=img/cover-kindle.jpg -o WYAH.epub title.md 0*.md
pandoc: Error running filter includes.hs
includes.hs: createProcess: runInteractiveProcess: exec: does not exist (No such file or directory)
Makefile:49: recipe for target 'epub' failed
make: *** [epub] Error 83

In the Parsing section, http://dev.stephendiehl.com/fun/parsers.html, you write "Recall that in Haskell in the String type is itself defined to be a list of Char values...", but you write it as a list of String values. That section should have single quotes instead:

"1+2*3"
['1','+', '2', '*', '3']

I was excited to see the introduction to modern Haskell as I find that it's very confusing to enter Haskell these days as many or most introductions doesn't actually match current practices (Text vs. String, cabal vs. plain GHC, etc). However, I was bewildered when the Cabal & Stack section didn't mention Stack. Is this merely waiting for someone to write it? At the very least, we should be able to toss in a paragraph with a pointer? (I haven't used it yet, so I'm a bad candidate to write it).

Thank you for you excellect book.
Could you generate an epub version of the book, that will be really helpful for portability ;)

In the Parsers chapter, under Lexer, lexer is defined as Tok.makeTokenParser emptyDef. Shouldn't this be Tok.makeTokenParser langDef, using the definition of langDef given above it?

I get [Math Processing Error] everywhere there is supposed to be (I guess) LaTeX. It looks like this:

I'm not sure if this is an issue with my browser (Firefox on OS X) or something else

It looks like the RSS feed for this book is incomplete.

Perhaps I'm doing something dumb, but I can't build any of the code (here is chapter7/poly but others don't build as well)

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.4
$ cabal --version
cabal-install version 1.22.0.0
using version 1.22.0.0 of the Cabal library 
$ cabal install
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: poly-0.1.0.0 (user goal)
next goal: base (dependency of poly-0.1.0.0)
rejecting: base-4.7.0.2/installed-bfd... (conflict: poly => base>=4.6 && <4.7)
rejecting: base-4.7.0.2, 4.7.0.1, 4.7.0.0, 4.6.0.1, 4.6.0.0, 4.5.1.0, 4.5.0.0,
4.4.1.0, 4.4.0.0, 4.3.1.0, 4.3.0.0, 4.2.0.2, 4.2.0.1, 4.2.0.0, 4.1.0.0,
4.0.0.0, 3.0.3.2, 3.0.3.1 (global constraint requires installed instance)
Dependency tree exhaustively searched.

Note: when using a sandbox, all packages are required to have consistent
dependencies. Try reinstalling/unregistering the offending packages or
recreating the sandbox.

Is there a greater reason for not supporting GHC 7.8?

I guess the text is formally correct (although it can be more precise) but the example is completely misleading: capture might happen if we do substitution under a lambda but in the example substitution comes from the beta-reduction and after the reduction lambda is gone! There is actually nothing bad to have that x in \FV{a}, for example: (\x. x) x -> x. On the other hand, bad things still might happen even if we check x \notin \FV{a}, for example: (\x. \y. xy) y -> \y. yy (capture!).
In fact, our substitution is defined to be capture-avoiding in the first place (condition in the last line of the definition ensures that), we probably just need an explanation that if the condition is not met it's always possible to alpha-convert the term such that substitution will be possible.

I am working through your wonderful "Write you a Haskell" tutorial, thanks a lot for creating it in the first place.

I have downloaded and compiled the code for chapter 4 (the untyped lambda calculus).

Contrary to the explanations in the text, SKK does not reduce to I in my case, instead I get:

Untyped> (\x y z. x z (y z)) (\x y . x) (\x y . x)
  => \x y z . (x z (y z))
  => \x y . x
 => \x y z . (x z (y z)) (\x y . x)
 => \x y . x
<<closure>>
Untyped>

Recall, that according to the text on page 50 I should see something along the lines of:

Untyped> (\x y z. x z (y z)) (\x y . x) (\x y . x)
  => \x y z . (x z (y z))
  => \y z . ((\x y . x) z (y z))
    => \x y . x
    => \y . z
   => z
 => \z . z
\z . z

I wonder what's going on? Cannot be a huge thing, as the data structures / code base
is relatively small at this point.

Nevertheless, as SKK=I is supposed to be a kind of litmus test, I would like to
get this fixed.

A few more explanations for what's going on in detail in Eval.hs would also be nice
(VClosure, Scope, type Eval = WriterT [Step](State EvalState) a, inc, red, etc)

Thanks.

l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$ stack build
write-you-a-haskell-0.1.0.0: build (exe)
Preprocessing executable 'write-you-a-haskell' for
write-you-a-haskell-0.1.0.0...
Cabal-simple_mPHDZzAJ_1.22.5.0_ghc-7.10.3: can't find source for Main in .

-- While building package write-you-a-haskell-0.1.0.0 using:
/home/l/.stack/setup-exe-cache/x86_64-linux-nopie/Cabal-simple_mPHDZzAJ_1.22.5.0_ghc-7.10.3 --builddir=.stack-work/dist/x86_64-linux-nopie/Cabal-1.22.5.0 build exe:write-you-a-haskell --ghc-options " -ddump-hi -ddump-to-file"
Process exited with code: ExitFailure 1
l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$

poly> 1 + 5
Cannot unify types:
        Int
with
        Int -> a

I think that the plus operator is not parsed correctly.

Rewrite poly text to reflect changes made in pull request #37

In chapter 4 the substitution application is written before the expression [x/a]e except in the section titled "Conversion and Equivalences".

My platform:
Ubuntu: 14.04
GHC: 7.8.4
cabal: 1.22.0.0
pandoc: 1.13.2
And all haskell related packages are installed with nix package manager.

When I tried to build the project, pandoc reported that
pandoc: Error running filter includes.hs fd:4: hPutBuf: resource vanished (Broken pipe) make: *** [000_introduction.html] Error 83

Chapter 6 in the section "Polymorphism" claims that it is impossible to write a function of type (a -> b) -> f a -> f b that doesn't satisfy forall f g. fmap f . fmap g = fmap (f . g). But this is false:

data F a = A a | B a

bad_fmap f (A x) = B (f x)
bad_fmap f (B x) = A (f x)

A result you do get from the free theorem for fmap is that fmap id = id <==> forall f g. fmap f . fmap g = fmap (f . g); that is, if your fmap satisfies one of the two functors laws then it necessarily satisfies the other one too. The above example satisfies neither.

I think the chapter on Hindley-Milner type inference needs to be pushed, the website has this code:

newtype TypeEnv = TypeEnv (Map.Map Var Scheme)

Whereas the chapter in git has this:

newtype TypeEnv = TypeEnv (Map.Map Name Scheme)

Thanks!

Hello!

I'm improving my knowledge in Haskell as the tutorial goes.
I followed the chapter 3 and looked the source in the repo.
The Main.hs file has a call to a function called ppexpr, that is defined in Pretty.hs.
The Pretty.hs has this line of code:

import Type

When I try to build it, GHC give me this error:

Could not find module `Type'
It is a member of the hidden package `ghc-7.8.3'.

By the name, it seems like it is some module WE would create, not a GHC Type module, but anyway, in my .cabal file, I added the line ghc >= 7.8.3, and everything blew up:

Warning: This package indirectly depends on multiple versions of the same
package. This is highly likely to cause a compile failure.
package ghc-7.8.3 requires transformers-0.3.0.0
package mtl-2.2.1 requires transformers-0.4.2.0
package haskeline-0.7.1.3 requires transformers-0.4.2.0 
package Compiler-1.0.0.2 requires transformers-0.4.2.0

Seems like GHC wants a different version of the package. This is strange...

How could I solve this?

Great job anyway! If someday I complete the whole tutorial, if I have time, I could translate it to Portuguese ;)

This is not parsed in the expected way in poly and poly_constraints:
(\f -> f 0 + f 1)
(\f -> if f 0 then f 1 else f 2)
It works with parens around the function applications.

The Evaluation chapter says

This value will be passed off to Haskell and reified into real world effects.

I believe this is somewhat confusing. In my understanding, that value is not reified into real world effects. On the contrary, it is a reification of real world effects, which can then be interpreted to actually cause those effects.
Or am I misunderstanding the concept of reification?

I think the expression variables and type variables have been mistakenly exchanged

• The outermost expression can't be a let expression:

Poly> let x=0 in x
"<stdin>" (line 1, column 11):
unexpected reserved word "in"
expecting letter or digit

• Unlike let declarations, let expressions don't allow function definitions with arguments:

Poly> (let f x = x in f 0)
"<stdin>" (line 1, column 8):
unexpected "x"
expecting "="

• let rec expressions aren't recursive:

Poly> (let rec x = x in x)
Not in scope: "x"

• Since fix is a special syntactic form that has to be applied to an expression, I expected g fix x not to parse. Instead, it is parsed as g (fix x).

You ever going to finish this? I've been waiting for this for years.

Add test cases to test.ml for pathological cases on pull request #40 issue

I'll preface this by saying that my knowledge of Haskell is intermediate at best, but the discussion on recursion seems to fall somewhere between misleading and wrong. Many recursive functions are not tail-recursive - the factorial example isn't, for instance. It's possible to transform function to be tail-recursive, but I would be surprised if such transformations are the default behavior of any Haskell compiler at -O0. I especially would hesitate to speculate on the implementation of recursion due to Haskell's laziness.

As a side note, the mutually recursive examples have extraneous semicolons.

In the Lambda Calculus chapter, under Substitution, there's first an explanation that in ((\x.e)a) x is replaced by a in e, also written as [x/a]e.
This is immediately followed by (\a.e)x -> [x/a]e which seems like the reverse of what's above to me.

Assuming the second notation is correct (so [x/a]e means 'occurrences of a in e are substituted by x', or ((\a.e)x)), the next example seems not to be in line: [y/x](\y.yx) would be 'occurrences of x in (\y.yx) are substituted by y, or (\y.yy), unlike the text which says (\x.xx), which is equivalent but could be confusing.

Overall: it might be just me but I believe there might be some inconsistencies in those paragraphs. I'd love to send a PR to fix, but I don't know what the proper fix would be.

In the process of implementing my own compiler, I found an inconsistency between the implementation of type inference between the poly and poly_constraints compilers in chapter 7.

I believe it has to do with the constraint generation around the "let" construct. In particular, let polymorphism doesn't seem to behave consistently.

A simple term that exhibits the problem is

let f = let add = \a b -> a + b in add

"poly" reports the type of "f" as "int -> int -> int," as it should be

"poly_constraints" reports it has type "forall a b c. a -> b -> c", which is too general.

Fix poly inference for If/Op per comments in pull request #33 .

Poly> let not x = if x then False else True
Poly> \x -> if (not x) then x else (x+1)
<<closure>> : Int -> Int

Poly> let b2i x = if x then 1 else 0
Poly> \x -> (b2i x) + x
<<closure>> : Int -> Int
Poly> (\x -> (b2i x) + x) 0
poly: Pattern match failure in do expression at Eval.hs:58:5-12

In the Introduction, under 'Functional Compilers', the pipeline graphic says 'Compliation', which should be 'Compilation'.

I intended to send a simple PR for this, but the sources seems to be missing from this repository?