Haskell – Where am I at?

A long list of scattered thoughts. I need more examples.

Functors:

fmap generalizes map on lists. If you can apply a function and inject it into a container it is a functor.

Examples: trees. Simple wrappers. Records.

Alternatively Functors are category theory functors. The combo of the type constructor (Which maps a into Constructor a) and fmap (which maps the morphisms)

Foldable:

foldMap is like concatMap.

I am confused.

Traversable:

traverse is like fmap except “effectful”?

traverse is like mapM for applicatives? Like a mapA. mapM is like map except it uses bind instead of apply. So if you had a list of Maybe Ints you could mapM over them to apply a monadically defined function Int -> mb to all elements. So instead you use <*> I guess? If you had a…

sequence is like? It flips outside and inside wrappers? List of Maybes to a Maybe List. Like transposing a matrix ? Hmm. The matrix is a bit confusing because there is a traversable and an applicative at play

I am confused.

Applicative:

slightly less powerful monads. Equal to do notation if you don’t use values until the return.

Applying a list of functions to a list of arguments. Either zipwise or nondeterministic/cartesian product wise.

If you fmap <$> a multiargument function over a list you get a list of functions via currying.

(+) <$> [1,2] <*> [7,8]

will return a list of all possible sum combos via the default applicative list instance.

I am pretty darn confused about applicative. I don’t have examples of applicatives that aren’t also monads although I’ve seen the claim there are many.

Lens:

Look at Simon Peyton Jones talk. It helped a lot. Ed Khmett’s talk is very puzzling from the get go. It assumes comfort levels with traversable and foldable.

Lens a b are kind of functiony “things” that have a big object a and a focus within that object b.

Simplest lens would be a hand written setter and getter functions

something like the _1 lens would look like

_1  {get = \(x,y) -> x, set a = \(_,y)->(a,y)}

Composable. Sort of compose setters and getters if one guy is inside of another. I think there is some pipework for getting set to work.

Can be unified into a single interface. Lens’ which uses Functorial trickery. Using trivial seeming Functors can be useful. Identity and Const.

Interesting connection between type level and value level.

fix, id, const and Fix Identity and Const

Recursion Schemes:

http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/

Nutso shit.

Maybe a start is to try to right fold in terms of fix. Don’t use recursion except fix

Bananas Barbed Wire territory. Paper is incomprehensible due to using Squiggol notation

fix f = let x= fx in x

let is a primitive construct of its own.

bottom is the value a function returns when it gets into an infinite loop (If we insist on things being for real mathematical functions that have to return). bottom is always a possible value. You can’t really return bottom in some sense because of the Halting problem being unable to determine if stuff will halt (although in special cases its possible btw).

https://en.wikibooks.org/wiki/Haskell/Denotational_semantics

Profunctors:

Seem really important. This is the most promising area for me to find a good approach to anyon models.

Contravariant Functors are functors where fmap kind of reverse what happens.

There is a related funniness where you would apply f then apply g but the composition is written g . f  The order is swapped in some kind of wonky way between application and composition

Wrapping Isomorphisms as type. The Product type of the map and inverse map of the isomorphism.

Monads:

Labelled arrows that aren’t quite functions. Partial functions, Linear functions, Nondeterministic functions, random functions, state dependent functions.

bind is an awful lot like function application $.

Useful technique: Dumb write all the stuff you need to pass around, then try and push it all onto the right hand side. state dumbly = s -> a -> (s’ , b) . Returns new state s’ and result b when given original state s and argument a.

DRYing up function pipework (always error checking in every function).

It might tend to be better to understand and use monads without delving into their definition. They form their own language. (DSL) Undoing do notation in your head is a nightmare

CoMonad:

contextual arrow instead of effectful arrow

duplicate instead of join

Monad Transformers:

Stacking monads. That’s all I got.

 

 

 

 

 

Some parsing in Haskell

http://dev.stephendiehl.com/fun/002_parsers.html

https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Parsing

http://book.realworldhaskell.org/read/using-parsec.html

> import Control.Applicative hiding (many)
> import Control.Monad (liftM, ap)
> import Control.Monad.Plus
I’m going based on http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf A paper on monadic parsing by Hutton. More than based. I’m copying code.
I’m just writing down what I think as I’m going through this paper.
So what is going on here.
A parser is a little guy that will try to pull off all it can that patches from a string. If it can’t find anything
it will return an empty list. If it can match more than one option, it’ll return a list of possibilities

It feels more like a little regular expression guy
Its kind of a combo of a state monad and the list monad.
The state is the current string that is left to be chewed up
the list monad is for nondeterminstic computation, it returns all possible results
One wonders if this could be constructed useful using monad transformers
Don’t know much aout those but that is how the feel. For composing multiple monads.
> newtype Parser a = Parser (String -> [(a,String)])
> parse (Parser x) = x

Now, why is the type a function? What is going to happen is we’re going to define a way to compose these little
functions in a way to build up the big parser from the little ones. The a type parameter is interesting.
Maybe it returns a token representing what it found. Or maybe it just returns the string that matches

> item :: Parser Char
> item = Parser (\cs -> case cs of
> “” -> []
> (c:cs) -> [(c,cs)])

So item produces a parser that will match any character.

How do we grab all items? Well we need to compose up a bunch of these item guys.
What we kind of want is something that feels like
item3 = item $ item $ item
This doesn’t work because the types in and out down’t match. So it needs to be a monad to replace function application $ with
the monaidc bind >>=

> instance Monad Parser where
> return a = Parser (\cs -> [(a,cs)])
> p >>= f = Parser (\cs -> concat [parse (f a) cs’ |
> (a,cs’) <- parse p cs])

return makes a trivial parser: A function that doesn’t change the string at all and returns the object a no matter what the string said.
The bind operation composes the operations. What does it need to do?
1. It needs to return a function String -> [(a,String)] wrapper in a Parser constructor
2. It needs to strip the left over string coming out of p’s function and pass it into the function f makes
3. f might need to know what came before it to decide what parser to makes?
4. For every possibility that comes out of p you need to try what comes out of (f a)

I think 4 is non obvious. We’ll see if I change my mind.

So he used a list comprehension. Not what I would’ve thought of. It’s clean though. Here’s a very shitty construction process

Needs to return a function from strings
p >>= f = Parser (\cs
Need to use (parse p) to start. Then we have that list [(a,cs’)]
p >>= f = Parser (\cs -> (parse p) cs )
Probably map over the list we need to do something for every element
p >>= f = Parser (\cs -> map (parse p) cs )
What are we applying? f I guess. We need to apply f the the first argument to make a parser. Now we have a list of parsers.
p >>= f = Parser (\cs -> map (f . fst) (parse p) cs )
Now get those functions out
p >>= f = Parser (\cs -> map parse (map (f . fst) (parse p) cs))
This is getting too long. Things are getting out of hand. So I define intermediate expressions.
Now apply them
p >>= f = Parser (\cs -> map fs (map snd acs)
where
acs = (parse p) cs
fs = map parse (map (f . fst) acs)

eh screw it

The list monad has a similar bind.
God Do I have to implement Functor too? Probably.

> instance Functor Parser where
> fmap = liftM

> instance Applicative Parser where
> pure = return
> (<*>) = ap

Monad is automatically a functor and applicatibe. I should look up the defintions of those functions
> p :: Parser (Char,Char)
> p = do {c <- item; item; d <- item; return (c,d)}

ghci returns
*Main> (parse p) “qwerty”
[((‘q’,’e’),”rty”)]

So to add parsers allows you to take different routes.
The zero parser does jack all

> instance MonadPlus Parser where
> mzero = Parser (\cs -> [])
> mplus f g = Parser (\cs -> (parse f) cs ++ (parse g) cs)

> instance Alternative Parser where
> (<|>) = mplus
> empty = mzero
> sat :: (Char -> Bool) -> Parser Char
> sat p = do c <- item
> if (p c) then (return c) else mzero

> findq = sat (== ‘q’)

*Main> parse findq “qwerr”
[(‘q’,”werr”)]
*Main> parse findq “werr”
[]

> char :: Char -> Parser Char
> char c = sat (c ==)

> string :: String -> Parser String
> string “” = return “”
> string (c:cs) = do char c
> string cs
> return (c:cs)
> many :: Parser a -> Parser [a]
> many p = many1 p mplus (return [])
> many1 :: Parser a -> Parser [a]
> many1 p = do a <- p
> as <- many p
> return (a:as)

*Main> parse (many (char ‘c’)) “yoyoyoc”
[(“”,”yoyoyoc”)]
*Main> parse (many (char ‘c’)) “ccyoyoyoc”
[(“cc”,”yoyoyoc”),(“c”,”cyoyoyoc”),(“”,”ccyoyoyoc”)]
> isSpace s = s == ‘ ‘ || s == ‘\t’ || s == ‘\n’ || s == ‘\r’
> space :: Parser String
> space = many (sat isSpace)

> token :: Parser a -> Parser a
> token p = do {a <- p; space; return a}

> symb :: String -> Parser String
> symb cs = token (string cs)

> apply :: Parser a -> String -> [(a,String)]
> apply p = parse (do {space; p})

> data Expr = Expr Addop Term | Term
> data Term = Val Int

and I’m tired So I’ll stop.

A whole new world. Propositions as types. Idris. Rule-rewriting


Fatal error: Uncaught Error: Call to a member function id() on array in /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_formatter.class.php:36 Stack trace: #0 /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_formatter.class.php(538): CrayonFormatter::format_code('', Array, Object(CrayonHighlighter)) #1 [internal function]: CrayonFormatter::delim_to_internal(Array) #2 /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_formatter.class.php(516): preg_replace_callback('#()#msi', 'CrayonFormatter...', 'g(3) = 4\r\nf(g(x...') #3 /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_highlighter.class.php(166): CrayonFormatter::format_mixed_code('g(3) = 4\r\nf(g(x...', Object(CrayonLang), Object(CrayonHighlighter)) #4 /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_highlighter.class.php(186): CrayonHighlighter->process() #5 /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_wp.class. in /home/public/wordpress/wp-content/plugins/crayon-syntax-highlighter/crayon_formatter.class.php on line 36