Автор Тема: Вопросы по Haskell  (Прочитано 15607 раз)

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Вопросы по Haskell
« : Октябрь 11, 2011, 08:22:30 am »
Периодически у меня возникают дурацкие вопросы, с которыми я не решился бы лезть на специализированный форум. Надеюсь, видные хаскелеводы здесь помогут чайнику.

Взял исходный текст задачи Эйнштейна здесь http://habrahabr.ru/blogs/Haskell/122123/ и скормил его WinGHCi 1.0.6. Запускаю Run "main", среда задумывается, потом выдает ответ. Ресурсы: (1.77 secs, 140068460 bytes)
Если запускать еще, то мгновенно выдается ответ, ресурсы (0.00 secs, 0 bytes). Что, вообще, происходит второй и все последующие запуски? Почему так быстро и без затрат памяти?


Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #1 : Октябрь 11, 2011, 08:29:36 am »
Кстати, вот текст. А то его получение из страницы на хабре - нетривиальная задача.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #2 : Октябрь 11, 2011, 10:50:44 am »
Взял исходный текст задачи Эйнштейна здесь http://habrahabr.ru/blogs/Haskell/122123/ и скормил его WinGHCi 1.0.6. Запускаю Run "main", среда задумывается, потом выдает ответ. Ресурсы: (1.77 secs, 140068460 bytes)
Если запускать еще, то мгновенно выдается ответ, ресурсы (0.00 secs, 0 bytes). Что, вообще, происходит второй и все последующие запуски? Почему так быстро и без затрат памяти?
Просто интерпретатор прокешировал результаты вычисления программы и печатает уже ранее вычисленное значение.
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #3 : Октябрь 11, 2011, 11:33:57 am »
Ах, ну да, побочных эффектов нет, функции можно смело кешировать.
Непривычно.

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #4 : Октябрь 11, 2011, 12:00:09 pm »
WinGHCi, кстати, это просто ГУИ-оболочка для GHCi.
Удобная консолька, но запоминает слишком большую историю команд, и не понятно как очистить ))

ЗЫ. GHCi, оказывается, тоже хранит историю ввода ))
« Последнее редактирование: Октябрь 11, 2011, 12:01:45 pm от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #5 : Октябрь 11, 2011, 12:09:45 pm »
А про WinHugs что-нибудь можете сказать? У него есть более-менее дружественный хелп, но текст задачи он не жрет.
Чем народ-то пользуется?

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #6 : Октябрь 11, 2011, 12:41:01 pm »
я лично обычно пользуюсь WinHUGS, но если он оказывается несовместим с той или иной программой на хаскелле (то ли расширение языка не поддерживает, то ли библиотеки не так реализованы или вообще отсутствуют), то компилирую в GHC. Реже GHCi или WinGHCi (когда вспоминаю про него).

У WinHUGS есть интересные фишки -- браузер классов, конструкторов и тд, в частности просмотрщик иерархий классов. Правда я этим добром почти не пользуюсь...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #7 : Октябрь 11, 2011, 12:50:11 pm »
А про WinHugs что-нибудь можете сказать? У него есть более-менее дружественный хелп, но текст задачи он не жрет.
Что бы Winhugs принял эту задачу, надо в начале файла после секции импорта вставить строку
default(Int)то есть начинаться этот файл должен так:
import Data.List (lookup,nub)
import Data.Maybe (fromMaybe,catMaybes)

default(Int)
Функция objectAt принимает на вход целое число типа Int, а по умолчанию целочисленные константы в выражениях принимают значение Integer, если у транслятора нет подсказок, что достаточно типа Int.

В данном случае в функции
-- один объект всегда следует за другим
before obj obj' = r_any [
  objectAt n obj <&> objectAt (n + 1) obj' | n <- [1..size - 1] ]
такой информации нет, и HUGS решает, что n и 1 в выражении objectAt (n + 1) obj' | n <- [1..size - 1] имеют тип Integer.
Этому выводу способствует неуказанный тип константы size, который принимается равным Integer.

GHC же более умный, учитывает тип функции objectAt и правильно обрабатывает такой случай.
Хотя по идее он тоже должен был ругнуться на это место.

Ещё WinHUGS решает эту задачу заметно медленнее, чем GHCi.
« Последнее редактирование: Октябрь 11, 2011, 12:52:36 pm от Geniepro »
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #8 : Октябрь 11, 2011, 01:29:21 pm »
Спасибо за подробное объяснение!

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #9 : Октябрь 12, 2011, 06:52:49 am »
Кстати, раз вас заинтересовала головоломка Энштейна, то может будет интересна и эта:

Мартин Эрвиг. Побег от Зурга: упражнение в логическом программировании
http://fprog.ru/lib/martin-erwig-escape-from-zurg/

Тут задачка попроще, и с более подробными объяснениями.
Перевод, правда, не ахти (я её переводил 4 года назад, при том что я сам не очень знаю этот ихний инглиш, да и хаскелл я тогда только начал изучать)...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #10 : Октябрь 12, 2011, 02:56:30 pm »
Спасибо.
Несмотря на то, что вторая задача проще, с первого взгляда я мало что понял в решении.
Если найду время, попробую решить эти задачи на императивном языке (C# в данном случае) и сопоставить решения с Haskell'ными.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #11 : Октябрь 24, 2011, 06:07:06 am »
Мартин Эрвиг. Побег от Зурга: упражнение в логическом программировании
http://fprog.ru/lib/martin-erwig-escape-from-zurg/
Просьба пояснить этот момент (первый вариант SearchProblem):
space s = step ++ expand step
      where step = [ ([m],t) | (m,t) <- trans s ]
            expand ss = [ (ms++ns,t) | (ms,s) <- ss,
                                       (ns,t) <- space s ]
"space s" определяется через "space s". Бесконечная рекурсия, насколько я понимаю.
В конце статьи во втором варианте SearchProblem на этом месте стоит trans s.

Есть ошибка, или это я торможу?

P.S. Видимо, второе, т.к. там речь идет о бесконечных конструкциях.
Ну, может во втором варианте ошибка?
« Последнее редактирование: Октябрь 24, 2011, 06:11:52 am от Peter Almazov »

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #12 : Октябрь 24, 2011, 10:32:12 am »
Просьба пояснить этот момент (первый вариант SearchProblem):
space s = step ++ expand step
      where step = [ ([m],t) | (m,t) <- trans s ]
            expand ss = [ (ms++ns,t) | (ms,s) <- ss,
                                       (ns,t) <- space s ]
"space s" определяется через "space s". Бесконечная рекурсия, насколько я понимаю.
В конце статьи во втором варианте SearchProblem на этом месте стоит trans s.

Есть ошибка, или это я торможу?

P.S. Видимо, второе, т.к. там речь идет о бесконечных конструкциях.
Ну, может во втором варианте ошибка?
Оба варианта правильные, вычисляют верно одно и тоже решение.

Тут проблема в так называемом "name hiding" -- в выражении
[ (ms++ns,t) | (ms,s) <- ss,
               (ns,t) <- space s ]
s -- уже не та s, что является параметром функции s. Она выбирается из переменной step в выражении
expand step
where step = [ ([m], t) | (m,  t)  <- trans s ]

Более наглядно, наверное, было бы записать этот код так:
    space s = step ++ expand step
      where step      = [ (   [m],   t) | (m,  t)  <- trans s ]
            expand ss = [ (ms ++ ns, t) | (ms, s') <- ss
                                        , (ns, t)  <- space s' ]
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #13 : Ноябрь 07, 2011, 09:29:51 am »
Я вот сейчас книгу по языку "Clean" читаю.
Clean -- хаскеллоподобный язык. Почему же не сам Хаскелл?

По сравнению с хаскеллом мне клин показался каким-то заумным -- одни только списки чего стоят: ленвые с начала, ленивые с конца, энергичные с начала... тьфу!
Уникальные типы, насколько я понял, не имеют преимуществ перед монадой IO, хотя и являются по мнению некоторых людей интересной концепцией.
Кстати, последняя реализация компилятора Clean имет возможность и хаскельные программы компилировать, но что-то я так и забыл посмотреть, как там оно... ;D
Я в Clean еще не врубился, но желание пока не пропало. Может, впереди и ждет разочарование. С другой стороны идея Хаскеля использовать монады для ввода-вывода мне вполне определенно не нравится.
Вся эта функциональщина продвигается ни шатко, ни валко, в свободное время.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Вопросы по Haskell
« Ответ #14 : Ноябрь 15, 2011, 10:19:50 am »
http://blog.ezyang.com/2011/11/how-to-read-haskell/
А ведь врет мужик:
Цитировать
Arguments. f a b c translates into f(a, b, c). Haskell code omits parentheses and commas.
f может иметь не 3, а 1 или 2 параметра и возвращать функцию. Тогда возможно
f(a)(b, c)
f(a,b)(c)