Haskell stackManip

stackManip.hs

{-
多行註解
-}
-- 單行註解

{-

We'll say that a stateful computation is a function that takes some state and returns a value along with some new state. 

    s -> (a,s)  

-}
type Stack = [Int]  
pop :: Stack -> (Int,Stack)  
pop (x:xs) = (x,xs)  
push :: Int -> Stack -> ((),Stack)  
push a xs = ((),a:xs)  

stackManip :: Stack -> (Int, Stack)  
stackManip stack = let  
    ((),newStack1) = push 3 stack  
    (a ,newStack2) = pop newStack1  
    in pop newStack2  
{-
    > stackManip [5,8,2,1]
    (5,[8,2,1])
-}


newtype State2 s a = State2 { runState2 :: s -> (a,s) }  
{-
    http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.ST.html#ST
    A State s a is a stateful computation that manipulates a state of type s and has a result of type a. 
    A computation of type ST s a transforms an internal state indexed by s, and returns a value of type a. 

    第一個 s 是一個外部輸入的狀態，執行後會得到一組 新的狀態s 跟 運算 result a
    根據 Monad 的定義 可以透過 bind (>>=) 來結合兩個 相同狀態 卻不同result a 的運算
-}
instance Functor (State2 s) where
    fmap :: (a -> b) -> State2 s a -> State2 s b 
    fmap f (State2 m) = State2 (\ p -> 
        let
        -- 透過將 State2 s a  裡存放的 function apply 到參數p 上  得到原本儲存於 State2 s a 的 (a, s)
        (r, new_s) = m p
        -- 之後再將 function f apply 到 a 上得到 b 則為 State2 s b 
        in (f r, new_s)
        )

{-
    > let a1 = pure 1 :: State2 Int Int
    > let a1Minus1 = fmap ((-)1) a1
    > runState2 a1Minus1 $ 5
    (0,5)
    -- 外部的 state 是 5 沒有改變
-}

ap2 :: (Monad m) => m (a -> b) -> m a -> m b
ap2 mf ma = do 
    f <- mf
    a <- ma
    return (f a) 
-- 注意這裡的 retrun 是包裝成 monad m

ap2' :: (Monad m) => m (a -> b) -> m a -> m b
ap2' mf ma =
    mf >>= (\ f ->
    ma >>= (\ a ->
    return (f a)))
-- 注意這裡的 retrun 是包裝成 monad m

instance Applicative (State2 s) where
    pure :: a -> State2 s a 
    pure x = State2 (\s -> (x, s))
    (<*>) :: State2 s (a -> b) -> State2 s a -> State2 s b 
    (<*>) = ap2

{-
    > let aPlus1 = pure (+1) :: State2 Int (Int -> Int)
    > let a2 = pure 2 :: State2 Int Int
    > runState2 (aPlus1 <*> a2) $ 100
    (3,100)
    -- 外部的 state 是 100 沒有改變
-}

instance Monad (State2 s) where  
    return :: a -> State2 s a 
    return a = State2 $ \s -> (a,s)  
    (>>=) :: State2 s a -> (a -> State2 s b) -> State2 s b 
    ssa >>= a_ssb = 
        State2 $ (\s -> 
        let sa = runState2 ssa
            (a, newState) = sa s  
            (State2 sb) = a_ssb a  
        in  sb newState)
{-
    首先將 sa function (s ->(a,s)) apply to 外部的 state s 上得到 (a, newState)
    之後將 a_sb function apply to a 上 得到 State2 裡的 sb function (s ->(b, s)) 
    最後將 sb function apply to newState 得到 (b, newState)

    從Type Signatrure 觀察得知 s 雖然 type 沒有改變，但是s內容已變成了 State2 s a 所改變了 
-}

pop2 :: State2 Stack Int  
pop2 = State2 $ (\ (sHead:sTail) -> (sHead, sTail) )  
-- pop2 外部輸入 state 將第一個 element 取出放在a的位置 隨後跟著新的 state s

push2 :: Int -> State2 Stack ()  
push2 a = State2 $ (\ s -> ((), a:s) )  
-- push2 則將新的輸入 a append 到state當中 ，在a的位置設定為 ()

{-
    pop2 的定義為 State2 Stack Int 是一個 concrete type
    但本質上一個包裝 function 的 box ，而 function 本身也能看成是一個 box
    使用時要先解開 State2 這層包裝才能取得裡面的 function apply 到外部的 State s上才能得到結果 
    
    push2 輸入一個Int參數 之後回傳 State2 Stack ()，只要外部State s輸入後，就會將 a 給加上去  
-}

stackManip2 :: State2 Stack Int  
stackManip2 = do  
    push2 3  
    a <- pop2  
    pop2  
{-
    > runState2 stackManip2 [5,8,2,1]
    (5,[8,2,1])
-}

stackManip3 :: State2 Stack Int  
stackManip3 =   
    push2 3 >>= (\ _-> 
    pop2 >>= (\ a -> 
    pop2 )) 
{-
    > runState2 stackManip3 [1,2,3]
    (1,[2,3])
-}

stackManip4 :: State2 Stack Int  
stackManip4 =  
    push2 3 >>= (\ _-> 
        -- pop2 >>= (\ a -> pop2 )
        State2 (\ s -> 
            let
                sa = runState2 pop2
                (a, newState) = sa s
                (State2 sb)   = (\a -> pop2) a
            in sb newState
        )
    ) 
{-
    > runState2 stackManip4 [1,2,3]
    (1,[2,3])
-}

stackManip5 :: State2 Stack Int  
stackManip5 =  
    State2 (\ s2 -> 
        let sa = runState2 (push2 3)
            (a, newState)   = sa s2
            -- ((), 3:s2) 其中s是外部的state  type為 Stack, 其 newStaet為 3:s2 !注意這裡是 Stack
            (State2 sb)     = 
                (\ _-> 
                    -- pop2 >>= (\ a -> pop2 )
                    State2 (\ s -> 
                        let sa = runState2 pop2
                            (a, newState) = sa s
                            (State2 sb)   = (\a -> pop2) a
                        in sb newState
                    )
                ) a
                {-
                    此時將 a = () 帶入, _ 其實就是 a = ()
                    其後可以直接觀察出(State2 sb) 對應的就是裡面的 \_-> 所回傳的
                    State2 (\ s -> 
                        let sa = runState2 pop2
                            (a, newState) = sa s
                            (State2 sb)   = (\a -> pop2) a
                        in sb newState
                    )
                -}
        in sb newState
        {-
            sb 帶入 newState 也就是
            (\ s -> 
                -- s 等於 3:s2
                let sa = runState2 pop2
                    (a, newState) = sa s
                    -- pop2 執行後 3:s2 變成 s2，把 3 pop出來 
                    (State2 sb)   = (\a -> pop2) a
                in sb newState
                -- 最後又將 s2 pop 一次，因此將s2拆成 s2x:s2xs 則結果為 (s2x, [s2xs]) 
            ) 3:s2
        -}
    )
{-
    > runState2 stackManip5 [1,2,3]
    (1,[2,3])
-}