Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Определите корректную функцию diff
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
sheldon sheldon вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2010
Question Определите корректную функцию diff - 10.11.2010, 01:19

В хаскеле ноль, но увы так сложилась судьба, что надо решить следующие задачки, помогите кто-нибудь чем сможите:


1. Работа с типом Expr. Используя тип Expr, определенный выше, реализуйте следующие функции (используйте для тестирования функцию parseExpr)
1) Определите корректную функцию diff, которая принимает в качестве дополнительного аргумента имя переменной, по ко торой необходимо осуществлять дифференцирование.
2) Определите функцию simplify, которая упрощает выражения типа Expr, применяя очевидные правила вида: • x + 0 = 0 + x = x • x • 1 = 1 • x = x • x • 0 = 0 • x = 0 • и т. д.
3) Определите функцию toString, преобразующую выражение типа Expr в строку. Например, результатом применения функции к выражению Add (Mult (Const 2) (Var "x")) (Var "y") должна быть строка "2*x+y". Учтите возможность использования скобок, например, выражение Mult (Const 2) (Add (Var "x") (Var "y")) должно преобразовываться в строку "2*(x+y)"
4) Определите функцию eval, которая принимает два параметра: выражение типа Expr и список пар типа (String,Integer), задающий соответствие имен переменных и их значений. Функция должна вычислять значение выражение с учетом заданных значений выражений. Например, выражение eval (Add (Var "x") (Var "y")) [("x",1),("y",2)] должно выдавать число 3.


2. Разработать тип данных, представляющий содержимое каталога файловой системы. Считаем, что каждый файл либо содержит некоторые данные, либо является каталогом. Каталог включает в себя другие файлы (которые, в свою очередь могут быть каталогами) вместе с их именами и размерами в байтах. В данной работе содержимое файлов можно игнорировать: тип данных должен представлять только их имена, размеры и структуру каталогов. Определите следующие функции:
1) dirAll, возвращающую список полных имен всех файлов каталога, включая подкаталоги.
2) find, возвращающая путь, ведущий к файлу с заданным именем. Например, если каталог содерит файлы a, b и c, и b является каталогом, содержащим x и y, тогда функция поиска для x должна вернуть строку "b/x".
3) du, для заданного каталога возвращающая количество байт, занимаемых его файлами (включая файлы в подкаталогах).



3. Теоретически возможно, хотя и неэффективно, определить целые числа с помощью рекурсивных типов данных следующим образом: data Number = Zero | Next Number Т. е. число является либо нулем (Zero), либо определяется, как число, следующее за предыдущим числом. Например, число 3 записывается как Next (Next (Next Zero)). Определите для такого представления следующие функции:
1) fromInt, для заданного целого числа типа Integer возвращающую соответствующее ему значение типа Number.
2) toInt, преобразующую значение типа Number в соответствующее целое число.
3) plus :: Number -> Number -> Number, свои аргументы.
4) mult :: Number -> Number -> Number, умножающую свои аргументы.
5) dec, вычитающую единицу из своего аргумента. Для Zero функция должна возвращать Zero.
6) fact, вычисляющую факториал.


4. Утверждением будем называть логическую формулу, имеющую одну из следующих форм:
• имя переменной (строка)
• p & q
• p | q
• ~p
где p и q — утверждения. Например, утверждениями являются следующие формулы:
• x
• x | y
• x & (x | ~y)
Разработайте тип данных Prop, представляющий утверждения такого вида. Определите следующие функции:
1) vars :: Prop -> [String], которая возвращает список имен переменных (без повторений), встречающихся в утверждениях.
2) Пусть задан список имен переменных и их значений типа Bool, например [("x",True),("y",False)].
Определите функцию truthValue :: Prop -> [(String,Bool)] -> Bool, которая определяет, верно ли утверждение, если переменные имеют заданные списком значения.
3) Определите функцию tautology :: Prop -> Bool, которая возвращает True, если утверждение верно при любых значениях переменных, встречающихся в нем (например, это выполняется для утверждения (x | ~x)).
Ответить с цитированием
  (#2 (permalink)) Старый
sheldon sheldon вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2010
По умолчанию 10.11.2010, 01:26

Заранее спасибо
Ответить с цитированием
  (#3 (permalink)) Старый
di4a di4a вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2010
По умолчанию 10.11.2010, 04:04

Особенно если можете помогите с задачей N3 из первого поста если не трудно, т.к. мне тоже горит, а хаскель явно не мой конек...

3. Теоретически возможно, хотя и неэффективно, определить целые числа с помощью рекурсивных типов данных следующим образом: data Number = Zero | Next Number Т. е. число является либо нулем (Zero), либо определяется, как число, следующее за предыдущим числом. Например, число 3 записывается как Next (Next (Next Zero)). Определите для такого представления следующие функции:
1) fromInt, для заданного целого числа типа Integer возвращающую соответствующее ему значение типа Number.
2) toInt, преобразующую значение типа Number в соответствующее целое число.
3) plus :: Number -> Number -> Number, свои аргументы.
4) mult :: Number -> Number -> Number, умножающую свои аргументы.
5) dec, вычитающую единицу из своего аргумента. Для Zero функция должна возвращать Zero.
6) fact, вычисляющую факториал.
Ответить с цитированием
  (#4 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 10.11.2010, 19:44

[CPP]data Number = Zero | Next Number deriving Show

dec (Next n) = n
dec _ = Zero

fromInt 0 = Zero
fromInt n = Next $ fromInt (n - 1)

toInt Zero = 0
toInt (Next n) = succ (toInt n)

plus Zero n = n
plus t n = Next (plus (dec t) n)

mult Zero _ = Zero
mult t n = plus n (mult (dec t) n)

fact Zero = Next Zero
fact n = mult n (fact (dec n))

[/CPP]


Don't fear the Monad
Ответить с цитированием
  (#5 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 10.11.2010, 19:48

2.
[CPP]data File = DataFile String Integer | Folder String [File] deriving Show

dirAll :: File -> [String]
dirAll (DataFile s _) = [s]
dirAll (Folder s xs) = [ concat [s, "|", ps] | ps <- dirAll `concatMap` xs]


find' :: String -> File -> [String]
find' s1 (DataFile s _) | s == s1 = [s]
find' s1 (Folder s xs) = [ concat[s, "|", ps] | ps <- find' s1 `concatMap` xs]
find' _ _ = []

du :: File -> Integer
du (DataFile _ x) = x
du (Folder _ x) = sum (du `map` x)[/CPP]


Don't fear the Monad
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 10.11.2010, 19:56

3.
[CPP]data Prop = And Prop Prop | Or Prop Prop | Not Prop | Var String deriving Show

vars :: Prop -> [String]
vars = nub . go where
go (And a b) = concat [go a, go b]
go (Or a b) = concat [go a, go b]
go (Not a) = go a
go (Var s) = [s]

unsafeLookup x t = case lookup x t of Just x -> x

truthValue table = go where
go (And a b) = go a && go b
go (Or a b) = go a || go b
go (Not a ) = not (go a)
go (Var a ) = unsafeLookup a table

gen [] _ = [[]]
gen(x:xs) ys = concat[(p `map` gen xs ys | p <- [(x, y) | y <- ys]]

tautology prop = all (flip truthValue prop) $ gen (vars prop) [True, False]
[/CPP]


Don't fear the Monad
Ответить с цитированием
  (#7 (permalink)) Старый
di4a di4a вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2010
По умолчанию 10.11.2010, 21:43

Огромное Вам СПАСИБО!!! все понятно и отлично работает=)
Ответить с цитированием
  (#8 (permalink)) Старый
sheldon sheldon вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.11.2010
Thumbs up 10.11.2010, 22:52

прикольно, вам на каждую задачу понадобилось меньше 10 минут...вы случайно не создатель хаскеля??)))
БОЛЬШОЕ БОЛЬШУЩЕЕ СПАСИБО
Да, кстати, вы не реализовали первую задачу, она трудная или вы решили, что даже такой балбес как я сможет её реализовать?
Ответить с цитированием
  (#9 (permalink)) Старый
Enlighter Enlighter вне форума
Новичок
 
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2010
По умолчанию 10.11.2010, 23:56

с дества не дружил с деревьями,если будет свободная минутка,посмотрите пожалуйста задачку..
Функции работы с бинарными деревьями поиска. Определите тип
данных, представляющий бинарные деревья поиска. В отличие от
деревьев, представленных в методических указаниях, в деревьях
поиска данные могут находиться не только в листьях, но и в проме-
жуточных узлах дерева. Будем использовать деревья для представ-
ления ассоциативного массива, сопоставляющие значения ключей
(представляемых как строки) целым числам. Для каждого узла с
некоторым ключом в левом поддереве должны содержаться элемен-
ты с меньшими значениями ключа, а в правом — с б´ ольшими. При
поиске соответствия между строкой и числом необходимо учиты-
вать эту информацию, поскольку она позволяет более эффективно
извлекать информацию из дерева. Определите описанный тип дан-
ных и следующие функции:
1) add, добавляющую в дерево заданную пару ключа и значения.
2) find, возвращающую число, соответствующее заданной стро-
ке.
3) exists, проверяющую, что элемент с заданным ключом со-
держится в дереве.
4) toList, преобразующая заданное дерево поиска в список,
упорядоченный по значениям ключей.
Ответить с цитированием
  (#10 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.11.2010, 12:25

Цитата:
Сообщение от sheldon Посмотреть сообщение
Да, кстати, вы не реализовали первую задачу
пиво кончилось
Цитата:
или вы решили, что даже такой балбес как я сможет её реализовать?
почему бы и нет.
Код:
data Expr = Const' Integer | Var String | Add Expr Expr | Mul Expr Expr deriving (Show, Eq)

fix' f x = 
  case f x of
    x' | x /= x' -> fix' f x'
    _            -> x  

is n = (Const' n ==)

simplify = fix' go where
  go expr = 
    case expr of
      Add x y 
        | is 0 x -> go y | is 0 y -> go x | otherwise -> Add (go x) (go y)
      Mul x y 
        | or [is 0 x, is 0 y] -> Const' 0
        | is 1 x -> go y | is 1 y -> go x | otherwise -> Mul (go x) (go y) 
      _       -> expr
        
toString expr =
      case expr of
        Const' n -> show n
        Var x    -> x
        Add x y  -> concat [toString  x, "+", toString  y] 
        Mul x y  -> concat [toString_ x, "*", toString_ y]
    where
      toString_ (Add x y) = concat ["(", toString x, "+", toString y, ")"] 
      toString_ e         = toString e
      
unsafeLookup x t = case lookup x t of Just x -> x
                                      
eval table = go where  
  go expr =
    case expr of 
      Const' n -> n
      Var x    -> unsafeLookup x table   
      Add x y  -> go x + go y
      Mul x y  -> go x * go y

flat_expr = fix' go where
  go expr =
    case expr of
      Mul x y ->  
        case (x, y) of
          (Add x1 y1, n) -> Add (Mul x1 n) (Mul y1 n) 
          (n, Add x1 y1) -> Add (Mul x1 n) (Mul y1 n) 
          _              -> Mul (go x) (go y)
      Add x y -> Add (go x) (go y) 
      _       -> expr

diff s = simplify . go . flat_expr where
  go expr = 
    case expr of
      Add x y  -> Add (go x) (go y)
      Mul x y -> 
        let 
          (n, ex) = entries s (Mul x y)  
        in
         Mul (Const' n) (if n > 1 then Mul (Var s) ex else ex)
      e -> Const' (fst $ entries s e) 
 
entries s (Var t) | t == s = (1, Const' 1)       
entries s (Mul x y) = 
  let 
    ((a, l), (b, r)) = (entries s x, entries s y) 
  in
   (a + b, Mul l r)
entries _ e  = (0, e)


Don't fear the Monad
Ответить с цитированием
  (#11 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.11.2010, 14:26

новый diff. вариант выше громоздок и неверен:
[CPP]diff s = simplify . go where
go expr =
case expr of
Var s' | s' == s = Const' 1
Add x y -> Add (go x) (go y)
Mul x y -> Add (Mul (go x) y) (Mul x (go y))
_ -> Const' 0[/CPP]


Цитата:
с дества не дружил с деревьями,если будет свободная минутка,посмотрите пожалуйста задачку..
Функции работы с бинарными деревьями поиска.
[CPP]data STree = Tip | Bin (String, Int) STree STree deriving Show

add (k, v) Tip = Bin (k, v) Tip Tip
add (k, v)(Bin (k1, v1) l r) =
if k > k1 then Bin (k1, v1) l (add (k, v) r)
else Bin (k1, v1) (add (k, v) l) r

find' k Tip = Nothing
find' k (Bin (k1, v1) l r)
| k == k1 = Just v1
| otherwise = find' k (if k > k1 then r else l)

exist k = isJust . find k

toList' Tip = []
toList'( Bin (_, v1) l r) = concat [toList' l, [v1], toList' r] [/CPP]


Don't fear the Monad
Ответить с цитированием
  (#12 (permalink)) Старый
Enlighter Enlighter вне форума
Новичок
 
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2010
По умолчанию 11.11.2010, 22:00

Большое спасибо, Вы меня действительно выручили)
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Enlighter Enlighter вне форума
Новичок
 
Сообщений: 9
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 10.11.2010
По умолчанию 25.11.2010, 15:22

Цитата:
Сообщение от calabi-yau Посмотреть сообщение
новый diff. вариант выше громоздок и неверен:
[CPP]diff s = simplify . go where
go expr =
case expr of
Var s' | s' == s = Const' 1
Add x y -> Add (go x) (go y)
Mul x y -> Add (Mul (go x) y) (Mul x (go y))
_ -> Const' 0[/CPP]




[CPP]data STree = Tip | Bin (String, Int) STree STree deriving Show

add (k, v) Tip = Bin (k, v) Tip Tip
add (k, v)(Bin (k1, v1) l r) =
if k > k1 then Bin (k1, v1) l (add (k, v) r)
else Bin (k1, v1) (add (k, v) l) r

find' k Tip = Nothing
find' k (Bin (k1, v1) l r)
| k == k1 = Just v1
| otherwise = find' k (if k > k1 then r else l)

exist k = isJust . find k

toList' Tip = []
toList'( Bin (_, v1) l r) = concat [toList' l, [v1], toList' r] [/CPP]
маленький вопрос: вводить надо сначала всё дерево,а потом функции, или можно данные взять из файла?
Ответить с цитированием
  (#14 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 25.11.2010, 17:01

Цитата:
Сообщение от Enlighter Посмотреть сообщение
маленький вопрос: вводить надо сначала всё дерево,а потом функции, или можно данные взять из файла?
можно ввести все, но можно и из файла, консоли, и.т.д.


Don't fear the Monad
Ответить с цитированием
  (#15 (permalink)) Старый
marinevladi marinevladi вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 11.11.2010
По умолчанию 02.12.2010, 18:13

А могли Вы и мне помочь с выше описанным типом expr:
1. как в консоли использовать функции "diff" и "eval", что-то не получается(скорее всего не правильно вызываю, как правильно не пойму...)
2.что именно делают функции "flat_expr" и "entries".
Заранее спасибо)))
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Определите функцию getTitle , возвращающую название товара sheldon Haskell 5 16.12.2011 12:26
Определите функцию APPEND, объединяющую два списка dudy Lisp 7 17.05.2011 22:53
Определите функцию, переворачивающую список deman Lisp 5 06.05.2011 16:37
Определите рекурсивную функцию MBR Pavel123 Lisp 0 20.12.2010 17:58
Определите функцию (f s), которая вычисляет список mario[x] Lisp 4 09.12.2010 15:37
Определите функцию (FIB N), вычисляющую N-й элемент последовательности Фибоначчи PATRI0T Lisp 4 08.11.2010 17:24
Определите функцию, удаляющую заданный элемент из списка Жасмин Lisp 1 26.10.2010 21:42
Определите функцию, зависящую от двух аргументов u и v lenochka90 Lisp 1 24.09.2010 14:21
Определите функцию, принимающую на вход целое число n AntiSemit Haskell 2 18.12.2009 17:54
Определите функцию (LINEN n), печатающую n раз квадрат 2*2 звездочками Чебурашка Lisp 1 12.12.2009 16:45
Определите функцию, зависящую от одного аргумента MaMasha Lisp 3 24.11.2009 13:44
С помощью предложений COND или CASE определите функцию imported_Irinka Lisp 2 15.05.2004 11:05



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов