Programistyczna zagadka

Thread View: pl.comp.lang.funkcyjne

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Michal Przybylek Fri, 25 Jul 2008 22:46

#946

Author: Michal Przybylek
Date: Fri, 25 Jul 2008 22:46

63 lines
2740 bytes

Poniżej kopia tego, co wysłałem przed chwilą na pl.comp.programming. Celem  
zabawy jest pokazanie, że jeżeli dostatecznie mocno się uprzeć, to nawet w  
Haskellu można wygodnie pisać w imperatywnym stylu.

***

Kiedy byłem studentem, jednym z ulubionych zadań gnębiących z semantyki i
weryfikacji, było podanie fragmentu programu w jakimś języku i pytanie o
to, co ten program robi. Ja proponuję trochę inną zabawę - poniżej jest
napisny mały program w Haskellu - oczywiście wiadomo co on robi. Pytaniem
jest dlaczego on robi to co robi. Miłej zabawy :-)


***
module Main (main)  where

import Control.Monad.Cont
import Control.Monad.State
import Data.Map
import IO (print)

infixr 0 <-:


-- nasze srodowisko bedzie zwyklym slownikiem odwzorowujacym
-- nazwy zmiennych w wartosci wstrzyknietym w monade stanu
getRef var = State $ \dict -> (Data.Map.lookup var dict, dict)
setRef var val = State $ \dict -> (Just val, insert var val dict)

-- podniesione przypisanie na zmienna / czytanie ze zmiennej
ref var = lift (getRef var)
var <-: val = lift (setRef var val)


-- definicja petli nieskonczonej
-- aby wykonac petle z cialem instr
--   wykonaj instr
--   wykonaj petle z cialem instr
loop :: ContT a (State s) a -> ContT a (State s) a
loop instr = instr >> loop instr


computeFact = callCC $ \exit ->
    loop $ do
      Just i   <- ref "i"      -- wez wartosc zmiennej "i"
      Just acc <- ref "acc"    -- wez wartosc zmiennej "acc"
      if i == 0
        then exit $ Just acc   -- wyskakujemy z petli z wynikiem acc
        else do
          "i"   <-: i-1        -- ustawiamy "i" na i-1
          "acc" <-: acc*i      -- ustawiamy "acc" na acc*i

fact n = k  where
    Just k = evalState (runContT computeFact return) initEnv
    initEnv = fromList [("i"  , n),
                        ("acc", 1)]

main = print $ fact 5

***

-- 
Michał Przybyłek

Re: Programistyczna zagadka

#947

Author: Michal Przybylek
Date: Sat, 26 Jul 2008 00:14

70 lines
2760 bytes

Dnia 26-07-2008 o 00:46:58 Michal Przybylek <michal.przybylek@gmail.com>  
napisał(a):

> -- definicja petli nieskonczonej
> -- aby wykonac petle z cialem instr
> --   wykonaj instr
> --   wykonaj petle z cialem instr
> loop :: ContT a (State s) a -> ContT a (State s) a
> loop instr = instr >> loop instr

Można oczywiście dać ogólniejszy typ, np.:
loop :: ContT a (State s) t -> ContT a (State s) u

Zagadka - jaki typ powstanie z rekonstrukcji?

> computeFact = callCC $ \exit ->
>     loop $ do
>       Just i   <- ref "i"      -- wez wartosc zmiennej "i"
>       Just acc <- ref "acc"    -- wez wartosc zmiennej "acc"
>       if i == 0
>         then exit $ Just acc   -- wyskakujemy z petli z wynikiem acc

Tutaj prościej jest wyskoczyć z samym "acc".

Podaję całość jeszcze raz z poprawkami:

***

module Main (main)  where

import Control.Monad.Cont
import Control.Monad.State
import Data.Map
import IO (print)

infixr 0 <-:


getRef var = State $ \dict -> (Data.Map.lookup var dict, dict)
setRef var val = State $ \dict -> (Just val, Data.Map.insert var val dict)

ref var = lift (getRef var)
var <-: val = lift (setRef var val)


loop instr = instr >> loop instr


{- glowny program -}

computeFact n = callCC $ \exit ->
   do
     "i"   <-: n                -- inicjalizujemy "i" na n
     "acc" <-: 1                -- inicjalizujemy "acc" na 1
     loop $ do
       Just i   <- ref "i"      -- wez wartosc zmiennej "i"
       Just acc <- ref "acc"    -- wez wartosc zmiennej "acc"
       if i == 0
         then exit acc          -- wyskakujemy z petli z wynikiem acc
         else do
           "i"   <-: i-1        -- ustawiamy "i" na i-1
           "acc" <-: acc*i      -- ustawiamy "acc" na acc*i

fact n =  runContT (computeFact n) return `evalState` empty

main = print $ fact 5


-- 
Michał Przybyłek

Re: Programistyczna zagadka

#948

Author: Michal Przybylek
Date: Sat, 26 Jul 2008 00:33

34 lines
2122 bytes

Dnia 26-07-2008 o 02:14:44 Michal Przybylek <michal.przybylek@gmail.com>  
napisał(a):

> computeFact n = callCC $ \exit ->
>    do
>      "i"   <-: n                -- inicjalizujemy "i" na n
>      "acc" <-: 1                -- inicjalizujemy "acc" na 1
>      loop $ do
>        Just i   <- ref "i"      -- wez wartosc zmiennej "i"
>        Just acc <- ref "acc"    -- wez wartosc zmiennej "acc"
>        if i == 0
>          then exit acc          -- wyskakujemy z petli z wynikiem acc
>          else do
>            "i"   <-: i-1        -- ustawiamy "i" na i-1
>            "acc" <-: acc*i      -- ustawiamy "acc" na acc*i

Tak jest jeszcze imperatywniej :-)


computeFact n = callCC $ \exit ->
   do
     "i"   <-: n                 -- inicjalizujemy "i" na n
     "acc" <-: 1                 -- inicjalizujemy "acc" na 1
     loop $ do
       Just i   <- ref "i"       -- wez wartosc zmiennej "i"
       Just acc <- ref "acc"     -- wez wartosc zmiennej "acc"
       when (i == 0) $ exit acc  -- wyskakujemy z petli z wynikiem "acc"
       "i"   <-: i-1             -- ustawiamy "i" na i-1
       "acc" <-: acc*i           -- ustawiamy "acc" na acc*i



-- 
Michał Przybyłek

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads