Нужна помощь в решении задачи на haskell

Jobs? А вообще где-то у меня была решена эта задача в чуть более общем виде…

Кстати, что вы называете цепными списками?

ну вот определение, которое я нашла: Самый простой цепной список — это последовательность однотипных элементов, которые произвольно расположены в памяти, а связываются друг с другом благодаря имеющейся в каждом объекте ссылке на следующий элемент. Ссылка у последнего элемента цепочки имеет какое-то специальное значение, по которому распознается конец списка.

Для работы с цепным списком нужно иметь ссылку на его голову — начальный элемент. В некоторых случаях удобно иметь еще и ссылку на последний элемент списка, — эта необходимость возникает, когда новые элементы нужно вставлять и в начало и в конец списка.

linked list

На лабу похоже... По-топорному вроде так можно (считая, что узлы и листья отличаются): либо совпадают, либо поддерево левой ветки, либо правой.

Помогите, пожалуйста, решить эту задачу на haskell
пожалуйста

Угу. Как говорит мой хороший друг «спасибо в кровать не положишь» (c). Сколько стоит подобная задача знаешь? http://www.kursovik.com/ в помощь

Всё просто, два дерева равны если равны их вершины и равны все поддеревья.

Второе дерево является поддеревом первого, если оно равно одному из поддеревьев первого.

А теперь пиши программу, извлекающую все поддеревья первого и сравнивающую их со вторым деревом. На хаскеле это пишется слово в слово как первые два предложения поста.

Можно предложить что-нибудь, что работает, но не получится подсунуть, скажем:

import Text.XML.HXT.Core

isSubTree :: (Eq (t a), Tree t) => t a -> t a -> Bool
isSubTree sub = not . null . runLA (deep $ isA (==sub))


main = print $ sub `isSubTree` tree

    where tree = fromString "<root><a>TextA<b>TextB</b></a><c>TextC</c></root>"
          sub  = fromString "<a>TextA<b>TextB</b></a>"

          fromString = head . runLA xread

извлекающую все поддеревья первого

Нахрена, когда можно рекурсивно?

Нахрена, когда можно рекурсивно?

А собственно какая разница, извлекаются эти поддеревья отдельно или мы рекурсивно проходим по поддеревьям сравнивая их со вторым деревом? Ну кроме разницы в производительности и потреблении памяти. Для студенческой домашки и так сойдёт.

«На декларативных языках код пишется в стиле ``что надо решить?``, а не ``как надо решить``».

Кажется, авторы этого тезиса чуток переоценили уровень будущих специалистов.

Дерево же, для него так и естественней и короче получается. Вот если не только поддерево найти, а еще какие-нибудь ф-ии написать, то отдельный генератор был бы удобен.

Изначально эта задача формулировалась для Lisp'а. Цепной список, видимо, — это «linked list», т.е. обычный список из cons-пар. Для хаскеля, естественно, придется использовать ADT.

почему не использовать List?

Ну [a] - тоже «algebraic».. Но ведь adt так красиво звучит, как можно устоять.

Я может туплю, но разве в Haskell уже появились нормальные гетерогенные списки?

лисповый cons это хацкелевый list. Поэтому на этом уровне ничего нового сочинять не надо, а как там дальше представлять это уже следующий вопрос. Я, кстати, вообще, плохо понимаю как можно правильно хранить дерево в списке, но возможно это сегодняшний экз по философии сказывается.

а так да, ADT простейший способ сделать замкнутый гетерогенный тип.

лисповый cons это хацкелевый list

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

Я, кстати, вообще, плохо понимаю как можно правильно хранить дерево в списке

вот и я о том же. Под структурой для дерева я имел в виду что-то типа такого:

data Tree a = Nil | Tree a [Tree a]

А если представлять в виде списка, то первое, что пришло в голову:

data TreeItem a = Item a | SubTree (Tree a) deriving (Show)

type Tree a = [TreeItem a]

Но и здесь, как видно, не обошлось без нового типа-суммы

лисповый cons это хацкелевый list.

Лисповый cons это хаскельный (,) :: * -> * -> *. А с учётом мутабельности - даже больше (cons-ы могут составлять граф, не дерево).

Я, кстати, вообще, плохо понимаю как можно правильно хранить дерево в списке

Я вот тоже не понял про «деревья в цепных списках», нормальное дерево это rose tree из containers. Для них:

import Data.Tree

subMatch :: Eq a => Tree a -> Tree a -> Bool
subMatch (Node x xs) (Node y ys) = x == y && and (zipWith subMatch xs ys)

subTree :: Eq a => Tree a -> Tree a -> Bool
subTree a b@(Node _ ys) = subMatch a b || or (map (subTree a) ys)

то первое, что пришло в голову

Почти :)

Точнее, вот так:

import Data.Tree

instance Eq a => Ord (Tree a) where
  a < b@(Node _ ys) = a == b || any (< a) ys

Лисповый cons это хаскельный (,) :: * -> * -> *. А с учётом мутабельности - даже больше (cons-ы могут составлять граф, не дерево).

спасибо, буду знать.

В HList даже такие лиспизмы используются:

data HNil = HNil
data HCons a b = HCons a b

хотя можно было обойтись () :: * и (,) :: * -> * -> *. И потом из этих конс-ов пытаются делать гетерогенные коллекции, но система типов, в общем-то, не позволяет. В том числе не позволяет замкнуть их в кольцо:

x = (1, y)
y = (2, x)

уже требует бесконечных типов.

a < b@(Node _ ys) = a == b || any (< a) ys

А толк от такого определения порядка? a < b && b < a - вполне может быть True

a < b && b < a - вполне может быть True

Тогда пусть будет нестрогое (<=) - рефлексивное, транзитивное и антисимметричное.