LINUX.ORG.RU

Очепятки в книге по функциональному программированию

 


1

3

В занимательной книженции Душкина «14 занимательных эссе о языке Haskell и функциональном программировании» в разделе про комбинаторы есть такой пример кода:

data Combinator = Var String
		| App Combinator Combinator
		| Lam String Combinator
  deriving Eq
instance Show Combinator where
  show (Var x)= x
  show (App x y) = case y of
     App _ _ -> showLam x ++
		"(" ++
		show y ++
		")"
     _	     -> showLam x ++
		showLam y
    where
	  showLam l@(Lam _ _) = "(" ++
	  			show l ++
				")"
	  showLam x	      = show x
  show (Lam x e) = "\\" ++
		   x ++
		   "."
		   ++ show e
i = Var "I"
k = Var "K"
s = Var "S"

free :: String -> Combinator -> Bool              
free x (Var y)	   = x == y
free x (App e1 e2) = free x e1 || free x e2
free x (Lam y e)   = free x e

transform :: Combinator -> Combinator
transform (Var x) = Var x
transform (App x y) = App (transform x)
                          (transform y)
transform (Lam x (Var y)) | x == y
  = i transform (Lam x e)
                          | (not . free x) e
  = App k (transform e) transform (Lam x l@(Lam y e))
                          | free x e
  = transform (Lam x (transform l))
transform (Lam x (App e1 e2))
  = App (App s (transform (Lam x e1)))
        (transform (Lam x e2))
Невооруженным глазом видны ошибки (естественно hugs его жрать отказывается). Тут е черт знает откуда взялась:
transform (Lam x (Var y)) | x == y
  = i transform (Lam x e)
Тут вообще синтаксически неверно:
                          | (not . free x) e
  = App k (transform e) transform (Lam x l@(Lam y e))
Я внес вот такие изменения:
transform :: Combinator -> Combinator
transform (Var x) = Var x
transform (App x y)= App (transform x)
						 (transform y)
transform e@(Lam x (Var y)) | x == y
  = App i (transform (Lam x e))
			  | (not . free x) e
  = App k (transform e) 
transform (Lam x l@(Lam y e))  | free x e
  = transform (Lam x (transform l))
transform (Lam x (App e1 e2))
  = App (App s (transform (Lam x e1)))
	(transform (Lam x e2))
Но как человек, увидевший haskell практически вчера, я своим изменениям естественно не доверяю. Правильно ли мне удалось уловить мысль автора?

Перемещено mono из talks

★★★
Ответ на: комментарий от monk

то shared_ptr — overkill

Почему? У меня тут нет лишних операций со счетчиком(shared_ptr передается по ссылке или как временный объект). Они будут только если ты начнешь ссылаться на одни и те же узлы из разных мест. И это вполне оправдано.

Можно auto_ptr вместо явного деструктора, но, ИМХО, код будет идентичен.

Не auto, у unique. В любом случае, будет проблема с копированием объектов, например.

А что плохого в operator<< ? По-моему более логичное соответствие Haskell'евскому Show.

Show он соответствует меньше, а вот подходу C++ как раз больше.

forCe
()
Ответ на: комментарий от monk

ADT — это инструмент

Согласен, именно об этом я и говорил. Только мне ещё кажется, что это инструмент такого же уровня фундаментальности как и, например, вложенные выражения или функции. Ну то есть можно рассуждать о том как бы мы писали на языке без вложенных выражений и функций, но зачем, это имеет смысл только если нам _надо_ писать на таком языке, но очевидно что это не будет проще или изящнее.

А на счёт реализации на C++ — попробуй теперь пример из топика, Очепятки в книге по функциональному программированию (комментарий) :) В хаскеле от примера с калькулятором до таких вещей — ерунда, потому что языковые средства располагают. Как и в SML, OCaml, F#, Scala или Rust, например. А, ну и Racket ещё.

quasimoto ★★★★
()
Последнее исправление: quasimoto (всего исправлений: 1)
Ответ на: комментарий от forCe

Если AST чуть более сложное, то в одну структуру упаковывать будет тяжко, как и union с тегами делать. В C++ и ООП вообще подход к expression problem на тему AST это обычно узлы в виде классов наследников от абстрактного класса интерфейса AST.

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Да, я так и делал в своих попытках навелосипедить языки=) Это было просто ответом на приведенный код.

forCe
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.