Добавить вершину с меткой в ярус дерева

@Lenoriya · Регистрация: 18.10.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Необходимо решить на Хаскеле задачу следующего содержания:
В указанном ярусе дерева добавить вершину с указанной меткой.

Ничего похожего не нашла(( Помогите, пожалуйста, или направьте в нужные русла...

@bokunopico · 30.03.2012, 00:36

Сообщение от Lenoriya

А вот уже строчка с let выдала ошибку.

Какой интерпретатор?

Сообщение от Lenoriya

Мне непонятен $

Отличное объяснение здесь, раздел Function application with $.

Code
1
2
($) :: (a -> b) -> a -> b  
f $ x = f x

Как ты уже перевела, ($) - применение функции f к аргументу x, то есть:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
fun :: Int -> Int   
fun n = n + 1
*Main> fun 10
11
*Main> fun $ 10
11
*Main> fun (10 + 2)
13
*Main> fun $ 10 + 2
13
*Main> :i $
($) :: (a -> b) -> a -> b   -- Defined in GHC.Base
infixr 0 $

Только этот оператор правоассоциативен и имеет самый низкий приоритет, что позволяет нам отказаться от скобок.

Code
1
Just $ Node n subtree r

эквивалентно:

Code
1
Just (Node n subtree r)

То есть сперва вызывается value-конструктор для дерева, а потом value-конструктор для АДТ Maybe.

Сообщение от Lenoriya

Не понимаю смысл точки

Та же ссылка, раздел Function composition.

Code
1
2
(.) :: (b -> c) -> (a -> b) -> a -> c  
f . g = \x -> f (g x)

Известная из математики композиция функций.

Code
1
2
3
4
5
6
7
8
9
10
f :: Int -> Int
f n = n + 1
g :: Int -> Int
g n = n * 2
*Main> f (g 2)
5
*Main> :t (f . g)
(f . g) :: Int -> Int
*Main> f . g $ 2
5

Code
1
Just . Node n l

Это функция, принимает на вход дерево (которое станет правой веткой узла n, то есть вызовется конструктор Node, результат которого передаётся в конструктор Just), возвращает дерево, завёрнутое в тип данных Maybe.

Code
1
2
*Main> :t (Just . Node 1 Empty)
(Just . Node 1 Empty) :: Num a => BinTree a -> Maybe (BinTree a)

P.S.: а монадическое связывание (>>=) тебя не смутило? >_<

@Lenoriya · 30.03.2012, 00:54 **[ТС]**

Преподаватель предложил только Hugs98, или Winhugs, не знаю как правильно)) Наверное из-за этого я никак и не сведу концы с концами...
Большое спасибо за объяснения =) Пока туго, но суть уловила. Завтра попробую во всём разобраться окончательно.
Про связывание не спрашивала, так как почитала статью какую-то и поняла, что не дано понять.

@bokunopico · 30.03.2012, 01:05

Сообщение от Lenoriya

Преподаватель предложил только Hugs98, или Winhugs

Добавь тогда в текстовый файл с кодом программы:

Code
1
x = Node 1 (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)) (Node 3 (Node 6 Empty Empty) (Node 7 Empty Empty))

А в интерпретаторе вызывай:

Code
1
*Main> insert x 2 100

Сообщение от Lenoriya

Про связывание не спрашивала, так как почитала статью какую-то и поняла, что не дано понять.

Молодец. Но если что - обращайся за советом, тебе, если что-то делаешь, обязательно помогут и объяснят.

@Nameless One · 30.03.2012, 04:13

Сообщение от Lenoriya

почему не перечислены входные данные?

в дополнение к объяснению выше: можно, не вдаваясь в подробности, сказать, что если у нас есть определение функции

Code
1
foo x y z = bar m x y z

То можно удалять с конца совпадающие переменные, и результат будет эквивалентным:

Code
1
foo = bar m

Так же и в моем коде, такое определение:

Code
1
insert tree level item = insert' True tree level item

можно безболезненно заменить на такое:

Code
1
insert = insert' True

Сообщение от Lenoriya

А вот уже строчка с let выдала ошибку.

Empty разделена символом перевода строки.

Сообщение от Lenoriya

Мне непонятен [...] subtree

subtree — это просто название переменной в ветке сопоставления по шаблону.

Сообщение от Lenoriya

Мне непонятен $. Что это вообще? Вроде как бакс означает не строгую переменную.

$ — оператор применения функции. f $ x означает то же применение функции f к аргументу x, как и (f x), но, в отличие от обычного применения функции (левоассоциативного с максимальным приоритетом), он правоассоциативен и имеет минимальный приоритет. Это позволяет без использования скобок для изменения приоритета выражения вычислить аргументы функции непосредственно перед применением функции к аргументам. Это позволяет сделать код более лаконичным.

Поэтому код

Code
1
Just $ Node n subtree r

Сначала вычисляет "Node n subtree r", потом применяет функцию-конструктор Just типа Maybe к результату вычисления. Результат аналогичен

Code
1
Just (Node n subtree r)

Сообщение от Lenoriya

Не понимаю смысл точки Just . Node n

начнем с того, что Maybe — это монада. Опять не вдаваясь в подробности, можно говорить, что в контексте монады Maybe запись

Code
1
f x >>= g

имеет смысл:

Code
1
2
3
case f x of
  Just result -> g result
  Nothing     -> Nothing

Т.е. если вызов функции слева от bind-оператора >>= вычислился в Nothing (а это означает «неудачу» в вычислениях), то возвращается Nothing. Иначе возвращается результат применения функции g к значению, «спрятанному» конструктором Just.

Теперь о записи

Code
1
Just . Node n l

Конструктор Node типа BinTree принимает три аргумента — значение узла, левое и правое поддерево. Т.к. функции в Haskell автоматически каррированы, то если передать конструктору только два аргумента, то он вернет функцию, принимающую последний аргумент и строящую значение данного типа. Таким образом, выражение "Node n l" вернет функцию которая принимает правое поддерево и строит значение типа BinTree. Точка в этой записи — это оператор композиции, который просто передаст результат вычисления выражения справа от себя функции слева от себя. Обобщая вышесказанное,

Code
1
Just . Node n l

— это функция, которая принимает (правое) поддерево и возвращает значение типа Maybe (BinTree a).

@bokunopico · 30.03.2012, 15:05

Сообщение от Nameless One

Empty разделена символом перевода строки.

Нет же, опытным путём установил, что WinHugs не может в связывание переменных в интерактивном режиме.

Code
1
2
Hugs> let x = 2
ERROR - Syntax error in expression (unexpected end of input)

Ошибка та же, да и GHCi, наверное, по-другому отреагировал бы.

Добавлено через 10 часов 34 минуты

Не по теме:

Code
1
2
3
*Main> let x = Node 1 (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)) Empty
*Main> insert x 2 100
Nothing

Хм. А я сразу и не обратил внимания на эту фишку со вставкой по крайней правой ветке.

@Nameless One · 30.03.2012, 17:22

Сообщение от bokunopico

А я сразу и не обратил внимания на эту фишку со вставкой по крайней правой ветке.

наверное, в таком случае, в один обход дерева задачу решить не получиться

@bokunopico · 30.03.2012, 17:31

Сообщение от Nameless One

наверное, в таком случае, в один обход дерева задачу решить не получиться

Да, в один проход было бы красиво (в принципе, и было).
Вообще задача часто встречается именно для Пролога, и судя по решению в теме Добавление вершины в указанный ярус дерева [Решено] [Турбо Пролог] (по комментариям к коду), там два прохода (или не два, у меня поверхностные знания языка).

Новые блоги и статьи Все статьи Все блоги /
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .
Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .	SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .

@Lenoriya 0 / 0 / 0 Регистрация: 18.10.2010 Сообщений: 55

	Добавить вершину с меткой в ярус дерева 28.03.2012, 20:10. Показов 3675. Ответов 26 Метки нет (Все метки) Здравствуйте! Необходимо решить на Хаскеле задачу следующего содержания: В указанном ярусе дерева добавить вершину с указанной меткой. Ничего похожего не нашла(( Помогите, пожалуйста, или направьте в нужные русла... 0

@Lenoriya 0 / 0 / 0 Регистрация: 18.10.2010 Сообщений: 55
	30.03.2012, 00:54 [ТС]
	Преподаватель предложил только Hugs98, или Winhugs, не знаю как правильно)) Наверное из-за этого я никак и не сведу концы с концами... Большое спасибо за объяснения =) Пока туго, но суть уловила. Завтра попробую во всём разобраться окончательно. Про связывание не спрашивала, так как почитала статью какую-то и поняла, что не дано понять. 0