[Haskell] CIS 194: Homework 9-12

Functors,Applicative Functors,Monad的概念并不好理解，CIS 194讲得实在不怎么样，推荐翻阅《Haskell 趣学指南》之后再来做课后题

functorsapplicativeHomeWork 10data/type/newtypeHomeWork 11

先介绍了一下kinds就是type的type
haskell的类型系统中，type就是不相交的值的集合，type class就是集合的集合
而Maybe则是一个*->*类型的type constructor

Prelude> :k []
[] :: * -> *
Prelude :k [] Int
[] Int :: *
Prelude> :k [Int]  -- special syntax for [] Int
[Int] :: *
Prelude> :k Tree
Tree :: * -> *

来点curried：

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
Prelude> :k JoinList
JoinList :: * -> * -> *

中缀运算符(->)也是function

Prelude> :k Int -> Char
Int -> Char :: *
Prelude> :k (->) Int Char
(->) Int Char :: *

然后是Functor，也就是函子
C++中的Functor实际上是将class提升为first lass functions
而Haskell中的函子则来自于范畴论，是对于*->*类型的抽象
维基百科：

在函数式编程中，函子（functor）是受到范畴论函子启发的一种设计模式，它允许泛化类型在内部应用一个函数而不改变泛化类型的结构。函子形成了更复杂的抽象如应用式、单子、Comonad的基础。

functor law 的第一条说明，如果我们对 functor 做 map id，那得到的新的 functor 应该要跟原来的一样。如果写得正式一点，他代表 fmap id =id。基本上他就是说对 functor 调用 fmap id，应该等同于对 functor 调用id 一样。
第二定律描述说先将两个函数合成并将结果 map over 一个 functor 的结果，应该跟先将第一个函数 map over 一个 functor，再将第二个函数 map over 那个 functor 的结果是一样的。正式地写下来的话就是 fmap (f . g)= fmap f . fmap g。或是用另外一种写法，对于任何一个 functor F，下面这个式子应该要被遵守：fmap (f . g) F = fmap f (fmap g F)。fmap的中缀同义词是(<$>)

class Functor f where
  fmap :: (a -> b) -> f a -> f b

关于IO的instance of Functor

instance Functor IO where
  fmap f ioa = ioa >>= (a -> return (f a))

这里隐含了（Monoid IO =>）
也就是实现了return，return 是一个Monoid wapper最终也就会返回IO (f a)
然后是申必的instance Functor ((->) e) where

fmap :: (a -> b) -> (e -> a) -> (e -> b)
instance Functor ((->) e) where
  fmap = (.)

但是不能用oop的思想理解这套type，因为haskell的类型系统保证了不需要遵守SOLID原则

SOLID 原则只是一套古人的朴素哲学思想，事实上这个领域还有其他（甚至是冲突的）哲学、玄学、禅学、道学思想。哲学的终极发展就是哲学的消解，就是形而上变成形而下，用科学探明了就不再需要哲学了。
里氏替换原则和三段论很相似，但它是对你而不是对编译器的要求。其提出源于一种问题：某些编程语言的类型虽然支持子类替换父类，但替换了代码不一定 work —— 为什么三段论的替换 works，而你的代码不 work？
这里有更深层次的原因：某些语言的类型系统很弱鸡，程序员给函数指定的类型并不能完全表达函数的行为。那解决方案就是用哲学训练人脑，编译器保证不了就用人脑保证。翻过来如果类型系统强到能完全表达函数的行为，编译器可以帮你检查你的 instance 是否替换正确，那么你也不需要时时记着这个里氏替换原则，于是科学上位而哲学消灭了。（你也可以忽略上面那些废话，记住“欲练神功，必先自宫”就好了，忘记所谓的 “OOP 思想”，世界会变得很简单。）
转回最初的具体问题，Haskell 的类型推导就是约束求解器，两个函数参数和结果都有约束，它给你填空填进符合约束的东西，就这么简单。
作者：luikore
链接：https://www.zhihu.com/question/437583966/answer/1659263054
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

下面的例子只是一个Functor class的instance而非functor

ghci> fmap id (CJust 0 "haha")
CJust 1 "haha"
ghci> id (CJust 0 "haha")
CJust 0 "haha"

上下文应用程序被称为applicative

在函数式编程中， 应用式函子，或简称应用式（applicative），是在函子和单子之间的中间结构。应用式函子允许函子式计算成为序列（不同于平常函子），但是不允许使用前面计算的结果于后续计算的定义之中（不同于单子）。应用式函子是范畴论中具有张量强度的不严格幺半群函子的编程等价者。

class Functor f => Applicative f where
	--应用式的pure方法，将值代入应用式
	pure  :: a -> f a
	-- 在应用式内部函数应用的等价
	(<*>) :: f (a -> b) -> f a -> f b
	pure  :: a             -> f a
	fmap  :: (a -> b)      -> f a -> f b
	fmap2 :: (a -> b -> c) -> f a -> f b -> f c
	--Now that we have (<*>), we can implement fmap2, which in the standard library is actually called liftA2:
	fmap f x = pure f <*> x
	liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
	liftA2 h fa fb = (h `fmap` fa) <*> fb

{- CIS 194 HW 10
   due Monday, 1 April
-}

module AParser where

import           Control.Applicative

import           Data.Char

-- A parser for a value of type a is a function which takes a String
-- represnting the input to be parsed, and succeeds or fails; if it
-- succeeds, it returns the parsed value along with the remainder of
-- the input.
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

-- For example, 'satisfy' takes a predicate on Char, and constructs a
-- parser which succeeds only if it sees a Char that satisfies the
-- predicate (which it then returns).  If it encounters a Char that
-- does not satisfy the predicate (or an empty input), it fails.
satisfy :: (Char -> Bool) -> Parser Char
satisfy p = Parser f
  where
    f [] = Nothing    -- fail on the empty input
    f (x:xs)          -- check if x satisfies the predicate
                        -- if so, return x along with the remainder
                        -- of the input (that is, xs)
        | p x       = Just (x, xs)
        | otherwise = Nothing  -- otherwise, fail

-- Using satisfy, we can define the parser 'char c' which expects to
-- see exactly the character c, and fails otherwise.
char :: Char -> Parser Char
char c = satisfy (== c)

{- For example:

*Parser> runParser (satisfy isUpper) "ABC"
Just ('A',"BC")
*Parser> runParser (satisfy isUpper) "abc"
Nothing
*Parser> runParser (char 'x') "xyz"
Just ('x',"yz")

-}

-- For convenience, we've also provided a parser for positive
-- integers.
posInt :: Parser Integer
posInt = Parser f
  where
    f xs
      | null ns   = Nothing
      | otherwise = Just (read ns, rest)
      where (ns, rest) = span isDigit xs

------------------------------------------------------------
-- Your code goes below here
------------------------------------------------------------
-- exercise 1
instance Functor Parser where
  fmap f (Parser rp) =Parser (fmap (first f)  . rp)

first :: (a->b) -> (a,c) -> (b,c)
first f (a,c) = (f a,c)

-- exercise 2
instance Applicative Parser where
    -- pure
    pure a = Parser f
        where f str = Just (a,str)
    -- apply
    p1 <*> p2 = Parser f
        where 
            f str = case runParser p1 str of
                        Nothing -> Nothing 
                        Just (fPro,strPro) -> fmap (first fPro)  (runParser p2 strPro)

-- exercise 3
abParser :: Parser (Char,Char)
abParser = (,) <$> char 'a' <*> char 'b'

abParser_ :: Parser ()
abParser_ = const() <$> abParser

-- exercise 4
instance Alternative Parser where
    empty = Parser (const Nothing)
    p1 <|> p2 = Parser f
                    where f str = runParser p1 str <|> runParser p2 str

-- exercise 5
intOrUppercase :: Parser ()
intOrUppercase = const () <$> posInt <|> const () <$> satisfy isUpper

 

data:
定义类型时可以有多个值构造子
newtype：
被限定为只能由一个值构造子和单一字段
但是没有解包的开销

newtype CoolBool = CoolBool { getCoolBool :: Bool }
--helloMe undefined不报错

type:
结构等价的同名构造，没有值构造子
相同类型的不同称谓

如果你只是希望你的 type signature 看起来比较干净，你可以只需要
type synonym。如果你想要将现有的类型包起来并定义成一个 type class 的
instance，你可以尝试使用 newtype。如果你想要定义完全新的类型，那你
应该使用 data 关键字。

{- CIS 194 HW 11
   due Monday, 8 April
-}

module SExpr where

import AParser

import Control.Applicative
import Data.Char

------------------------------------------------------------
--  1. Parsing repetitions
------------------------------------------------------------

zeroOrMore :: Parser a -> Parser [a]
zeroOrMore p = oneOrMore p <|> pure []

oneOrMore :: Parser a -> Parser [a]
oneOrMore p = (:) <$> p <*> zeroOrMore p
-- equivalent to:
{-oneOrMore p = liftA2 (:) p (zeroOrMore p-}

------------------------------------------------------------
--  2. Utilities
------------------------------------------------------------

spaces :: Parser String
spaces = zeroOrMore (satisfy isSpace)

ident :: Parser String
ident = liftA2 (:) (satisfy isAlpha) (zeroOrMore $ satisfy isAlphaNum)

------------------------------------------------------------
--  3. Parsing S-expressions
------------------------------------------------------------

-- An "identifier" is represented as just a String; however, only
-- those Strings consisting of a letter followed by any number of
-- letters and digits are valid identifiers.
type Ident = String

-- An "atom" is either an integer value or an identifier.
data Atom = N Integer | I Ident
  deriving Show

-- An S-expression is either an atom, or a list of S-expressions.
data SExpr = A Atom
           | Comb [SExpr]
  deriving Show

parseSExpr :: Parser SExpr
parseSExpr = spaces *>
              ( (A <$> parseAtom)
              <|>
              (char '(' *> (Comb <$> oneOrMore parseSExpr) <* char ')') )
             <* spaces

parseAtom :: Parser Atom
parseAtom = N <$> posInt <|> I <$> ident