Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
А в каком месте кода зарыто вычисление выражения согласно приоритетам операций +,-,*,/ ?
Здравствуйте, NotGonnaGetUs, Вы писали:
NGG>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
NGG>А в каком месте кода зарыто вычисление выражения согласно приоритетам операций +,-,*,/ ?
согласно поставноке приоритеты всех операций одинаковы, в частности обрати внимание на вычисление ячейки A2 в примере. если бы постановка была с приоритетамим, я бы разбил строку с выражением сначала на группы по младшим операциям, затем по старшим внутри каждой группы
Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
Ну что, дружище, чисто как архитектор архитектору, а также как автор задачи К, предназначенной для отбора Людей К, прокомментирую тебе твое решение.
1) Во вводной части жжошь. Еще пиши.
2) Хорошо что ты расшырил тестовий кейс. Предполагалось, правда, что при решении автор должен разработать набор тестов, дабы показать, как он то умеет делать, ну да ладно, мы, Люди К, слишком ленивы, чтобы делать тупую работу.
3) В целом, ты почти все технические грабли обошел. Остались уже нюансы для Людей К с чорным поясом. Проверь на своей программе вот такой пример:
'Text 25
=a1 =a2 =a1+a3
где клетка а1 — пуста. Что выведет твоя программа, и что, по твоему, она должна вывести (внимательно проанализируй ТЗ).
4) Где в твоем решении дизайн, мать его? Или на Хаскеле так и надо писать большие программы — вот будешь ты, допустим, писать взрослый excel с объемным ТЗ — ты тоже все в один модуль свалишь, и сделаешь все на функциях и вариантах?
Здравствуйте, Gaperton, Вы писали:
G>3) В целом, ты почти все технические грабли обошел. Остались уже нюансы для Людей К с чорным поясом. Проверь на своей программе вот такой пример: G> 'Text 25 G>=a1 =a2 =a1+a3
G>где клетка а1 — пуста. Что выведет твоя программа, и что, по твоему, она должна вывести (внимательно проанализируй ТЗ).
во-первых, ТЗ несколько неудобно с точки зрения тестирования, обмена тесатми и т.д. я изменил его — ячейки разделяются любым кол-вом пробелов/табуляций, а пустая ячейка записывается как "". вот рез-т:
Text 25 ""
#EVAL #EVAL #EVAL
всё верно, хотя сообщения об ошибке и маловразумительны. вообще, я не забыл ввести отдельные типы для ошибок/пустых ячеек/строк и сделал универсальную систему отлова ошибок — по исключениям
G>4) Где в твоем решении дизайн, мать его? Или на Хаскеле так и надо писать большие программы — вот будешь ты, допустим, писать взрослый excel с объемным ТЗ — ты тоже все в один модуль свалишь, и сделаешь все на функциях и вариантах?
во-первых, дизайн != разделению на отдельные файлы модули в моей программе обозначены либо секциями (библиотека, типы данных), либо глобальными функциями. далее, задача сформулирована в чисто функциональном стиле — это некое преобразование данных, и архитектура её решения в функциональном стиле — это декомпозиция сложного преобразования на более прочтые, используя стандартные комбинаторы типа (.) и map
мне имхается, что разобраться в устройстве программы несложно, а это и есть признак хорошего дизайна (а не следование каким-то стандартам, тем более выработанным для других стилей программирования). т.е. если читателю понятно каждое отдельное преобразование и понятно, как их комбинация позволяет получить требуемый результат — значит, цель достигнута
и собственно, я замахнулся на публикацию в вики именно потому, что посчитал это наглядной демонстарцией использования именно функционального подхода к решению задач — даже тех, которые большинство программитсов считает чисто императивными (отслеживание цикличных ссылок). кстати, опять же моё решение этой проблемы лучше в том плане, что оно не слито с другими модулями — вычисление значения выражения, как у thesz/geniepro, или возврата значения ячейки, как у тебя
множество простых, независимых друг от друга модулей, каждый из которых решает простую, ясно очерченную задачу — это и есть хороший дизайн
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
G>>3) В целом, ты почти все технические грабли обошел. Остались уже нюансы для Людей К с чорным поясом. Проверь на своей программе вот такой пример: G>> 'Text 25 G>>=a1 =a2 =a1+a3
G>>где клетка а1 — пуста. Что выведет твоя программа, и что, по твоему, она должна вывести (внимательно проанализируй ТЗ).
BZ>во-первых, ТЗ несколько неудобно с точки зрения тестирования, обмена тесатми и т.д. я изменил его — ячейки разделяются любым кол-вом пробелов/табуляций, а пустая ячейка записывается как "". вот рез-т:
Стоп.
1) Пустая ячейка должна записываться как пустая ячейка, то есть две табуляции подряд. Твоя программа это обрабатывает? Если нет (уверен что нет) — это ошибка в трактовке ТЗ.
2) В ТЗ не сказано, что пробел может являться разделителем ячеек. Там сказано, что разделителем является табуляция. Одна. Ты расширил ТЗ, что привело к неверной трактовке пустой ячейки.
Ай-ай. Если ты читал комменты к задаче в блоге Зефирова, там акцентруется внимание на то, что задача проверяет умение работать с ТЗ. Это трактуется как ошибка. Нефатальная, впрочем.
BZ>Text 25 "" BZ>#EVAL #EVAL #EVAL
BZ>всё верно, хотя сообщения об ошибке и маловразумительны. вообще, я не забыл ввести отдельные типы для ошибок/пустых ячеек/строк и сделал универсальную систему отлова ошибок — по исключениям
Это я заметил, это перечисленное у тебя сделано грамотно. Я этот тест тебе дал по другой причине. Правильный результат такого теста —
"tab Text tab 25" либо "tab Text tab #EVAL"
Почему так. Операции над строками запрещены, это верно. Однако в выражении =a2 нет никаких операций.
Что касается выражения =а1 — здесь нет ни строк, ни операций. Почему error? Обоснуй.
Третий пункт — неполнота ТЗ. В ТЗ не указано, как трактовать пустую ячейку. Предполагается, что на это человек должен обратить на неполноту внимание (либо описать этот case в сопроводиловке, что он трактует эту операцию как ошибку, либо, что гораздо интереснее, приводить пустую ячейку к 0 при арифметических операциях, как это делает взрослый excel).
В принципе, при отборе Людей К это ошибками не считали — просто обращали внимание на это при беседе, и спрашивали, как человек будет учитывать этот факт в своей программе.
G>>4) Где в твоем решении дизайн, мать его? Или на Хаскеле так и надо писать большие программы — вот будешь ты, допустим, писать взрослый excel с объемным ТЗ — ты тоже все в один модуль свалишь, и сделаешь все на функциях и вариантах?
BZ>во-первых, дизайн != разделению на отдельные файлы модули в моей программе обозначены либо секциями (библиотека, типы данных), либо глобальными функциями. далее, задача сформулирована в чисто функциональном стиле — это некое преобразование данных, и архитектура её решения в функциональном стиле — это декомпозиция сложного преобразования на более прочтые, используя стандартные комбинаторы типа (.) и map
Не разделению на файлы, а на модули и ADT. Модуль != файл. У модуля интерфейс есть. Дизайн — это составные блоки систем с четко прописанными функциями и интерфейсами. Просто представь, что объем функциональности разросся раз в 10, и покажи явно, как ты разделишь код на модули и какие будут интерфейсы, с объяснением простым человеческим языкм, почему сделал именно так — и все. Представь, что тебе надо ТЗ на эти модули выдавать разным разработчикам, а потом стыковать результат. Какой информацией ты их снабдишь? Не будешь же ты в один модуль все сваливать на большой задаче — так?
BZ>мне имхается, что разобраться в устройстве программы несложно, а это и есть признак хорошего дизайна (а не следование каким-то стандартам, тем более выработанным для других стилей программирования). т.е. если читателю понятно каждое отдельное преобразование и понятно, как их комбинация позволяет получить требуемый результат — значит, цель достигнута
+1, ты прав. Только у хорошего дизайна есть еще свойства помимо этого — независимые от языков и парадигм.
2) Для понимания одной составной части программы ("модуля", "компонента", класса, whatever) не должно требоваться понимать весь дизайн (требуется минимум знаний об остальной системе). Сформулировав решение таким образом, ты эффективно борешься со сложностью проблемы, декомпозировав ее на набор оносительно независимых мелких проблем, которые ты можешь поручить разным людям/командам, откуда следует пункт...
3) Хороший дизайн приводит к плану разработки с набором относительно независимых задач, который хорошо параллелится. И...
4) Цена внесения изменений в хороший дизайн низка (следствие п 2) — ведь при нем человеку не надо понимать всю твою программу, чтобы внести правку. Правка локальна для модуля ("компонента", класса, whatever).
BZ>и собственно, я замахнулся на публикацию в вики именно потому, что посчитал это наглядной демонстарцией использования именно функционального подхода к решению задач — даже тех, которые большинство программитсов считает чисто императивными (отслеживание цикличных ссылок). кстати, опять же моё решение этой проблемы лучше в том плане, что оно не слито с другими модулями — вычисление значения выражения, как у thesz/geniepro, или возврата значения ячейки, как у тебя
BZ>множество простых, независимых друг от друга модулей, каждый из которых решает простую, ясно очерченную задачу — это и есть хороший дизайн
Согласен. Тока есть design, и detailed design (по классификации PSP/TSP — описано в моем первом посте в блоге по проблеме К), которые лучше не путать. Последний у тебя хорош. Вот и выдели модули явно, с прописыванием интерфейсов, штоб видно было компоненты и их контракты друг перед другом. Хороший design можно показать "с птичьего полета".
Правда, там тоже нет явного разбиения на кучу малюсеньких модулей, всё в одном файле...
Но в принципе, программу визуально вполне можно разделить на четыре части, которые, впрочем, довольно тесно связаны друг с другом...
На Ваш тест
2 3
'Text 25
=A1 =A2 =A1+A3
программа даёт такой ответ:
Text 25
#Expr
Правда, расширенный пример Булата всё ещё приводит к переполнению стека, я над этим думаю.
Хочется решить это в рамках стандартного Хаскелла, а библиотека графов к стандартной вряд ли относится...
я потом этот приницп и в C++ использовал, только заменил type classes на templates, которые образовывали целую сеть с взаимодействующими интерфейсами, в т.ч. цикличными
Я повторюсь снова, но вот разве нет каких-либо внятных статей/книжек посвящённых именно правильному дизайну программных систем, про возможные подходы и т.п.?
В голову приходят только всякие Бучи да банды четырёх, но это лишь конкретные техники, они ведь особо не поясняют, к примеру, где именно лучше провести границы между классами и т.п.
Насколько я понимаю, по сути этот дизайн и должен быть одной из основных задач архитектора программных систем.
Здравствуйте, Курилка, Вы писали:
К>Я повторюсь снова, но вот разве нет каких-либо внятных статей/книжек посвящённых именно правильному дизайну программных систем, про возможные подходы и т.п.?
Самая внятная статья на эту тему написана Дэвидом Парнасом 35 лет назад.
"On the Criteria To Be Used in Decomposing Systems into Modules"
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>Здравствуйте, Gaperton, Вы писали:
BZ>>хочешь хорошего дизайна — посмотри на http://haskell.org/haskellwiki/Library/Streams
К>Я повторюсь снова, но вот разве нет каких-либо внятных статей/книжек посвящённых именно правильному дизайну программных систем, про возможные подходы и т.п.? К>В голову приходят только всякие Бучи да банды четырёх, но это лишь конкретные техники, они ведь особо не поясняют, к примеру, где именно лучше провести границы между классами и т.п.
Паттерны — идут лесом сразу. Проектировать они не учат.
По концепции АТД — лучшая книга "Использование абстракций и спецификаций при разработке программ", основанная на курсе лекций самой Барбары Лисков в MIT в конце 70 годов. Переведена на русский. Идею использовать электронную таблицу в качестве задачи на дизайн я взял оттуда — там она проходит как семестровая практическая работа для группы из 5 человек, и существенно более наворочена и функциональна. Кроме дизайна — эта книга также учит процессу разработки, и спецификациям программ. Великолепная книга.
По ОО проектированию — лучшая книга из тех что я видел — Object Modeling Technique, Rumbaugh. Появилась задолго до UML, OMT была самой популярной методологией моделирования до UML, книга — the best of the best of the best, единственная книга, которая реально учит дизайну. Там в конце каждой главы офигенный список задач на проектирование и моделирование. Хороших задач, непростых. Rumbaugh — гений и гуру. Чего стоят одни только его статьи — по сравнению с ним труды Буча — это младенческий лепет и научно-популярная литература.
На русский не переводилась.
Также любопытен подход CRC Cards — обязателен к изучению для любого проектировщика и архитектора. Это единственный подход, который позволяет описать объектную систему с высоты "птичьего полета" — пренебрегая несущественными деталями, и оставляя суть. Набор CRC-карт для вашей системы — это квинтэссенция ее дизайна. Это выше уровнем, чем модели UML и OMT. Мы ее применяли как для языка, описывающего дизайн на раннем этапе, так и как лучшее средство документирования кода (CRC-карты писались в коде в комментариях к основным классам — единственно возможный подход не потерять информацию о дизайне при эволюции системы).
Но это на все — основное в проектировании на самом деле, это анализ сценариев использования системы — use cases. Это главное, если вы его не выполняете, то вы не в состоянии верифицировать ваш дизайн. Книг на эту тему порекомендовать не могу, но классический автор по этой теме вроде как Якобсон.
К>Насколько я понимаю, по сути этот дизайн и должен быть одной из основных задач архитектора программных систем.
Архитектор обязан уметь кодировать лучше остальных, дизайнить лучше остальных, ловить ошибки лучше остальных, просчитывать последствия архитектурурных решений лучше остальных, знать предметную область и ее проблематику лучше остальных, а также владеть основами управления проектами и управления требованиями. Его основная задача — технически обчеспечить успешное выполнение проекта большой группой людей.
Здравствуйте, Gaperton, Вы писали:
G>По концепции АТД — лучшая книга "Использование абстракций и спецификаций при разработке программ", основанная на курсе лекций самой Барбары Лисков в MIT в конце 70 годов.
оп-па. вот так и оказывается, что я просто читал правильные книги в детстве, а не сам такой умный
G>Архитектор обязан уметь кодировать лучше остальных, дизайнить лучше остальных, ловить ошибки лучше остальных, просчитывать последствия архитектурурных решений лучше остальных, знать предметную область и ее проблематику лучше остальных, а также владеть основами управления проектами и управления требованиями. Его основная задача — технически обчеспечить успешное выполнение проекта большой группой людей.
а если в группе есть девушки, он должен лучше остальных ... ?
Здравствуйте, Gaperton, Вы писали:
G>По концепции АТД — лучшая книга "Использование абстракций и спецификаций при разработке программ", основанная на курсе лекций самой Барбары Лисков в MIT в конце 70 годов. Переведена на русский. Идею использовать электронную таблицу в качестве задачи на дизайн я взял оттуда — там она проходит как семестровая практическая работа для группы из 5 человек, и существенно более наворочена и функциональна. Кроме дизайна — эта книга также учит процессу разработки, и спецификациям программ. Великолепная книга.
Ага, видал такое, кстати у неё недавно книжка с явой вышла.
Из отзывов:
..."development in Java" means that Java is the vehicle, not the topic being taught
Здравствуйте, Gaperton, Вы писали:
G>Идею использовать электронную таблицу в качестве задачи на дизайн я взял оттуда
А я как раз спросить хотел, а не оотуда ли задачка?
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Gaperton, Вы писали:
G>>Идею использовать электронную таблицу в качестве задачи на дизайн я взял оттуда Т>А я как раз спросить хотел, а не оотуда ли задачка?
Дык! Задачка строго говоря не оттуда — я два дня условие составлял, чтобы убрать по максимуму кодирование и оставить проблемы дизайна, и сократить время решения задачи до 2-3 дней (в оригинале там задача на семестр на группу из 5 людей), а вот тема задачки и идея использовать для проверки дизайна электронную таблицу — безусловно взята оттуда. Лисков дурного не посоветует.
Я вот тут подумал, а что если ввести в эту электронную таблицу логические операции && || и операции сравнения > < >= <= == /= ... Что это даст? Можно ли будет с их помощью вычислить такие вещи, фибоначчи, факториал. аккермана и простые числа? Ведь макросов нету, циклов нету, циклические ссылки отбраковываются... Как их вычислять-то в таких условиях? А как вычислить их в Экселе, не пользуясь макросами?
G>Также любопытен подход CRC Cards — обязателен к изучению для любого проектировщика и архитектора. Это единственный подход, который позволяет описать объектную систему с высоты "птичьего полета" — пренебрегая несущественными деталями, и оставляя суть. Набор CRC-карт для вашей системы — это квинтэссенция ее дизайна. Это выше уровнем, чем модели UML и OMT. Мы ее применяли как для языка, описывающего дизайн на раннем этапе, так и как лучшее средство документирования кода (CRC-карты писались в коде в комментариях к основным классам — единственно возможный подход не потерять информацию о дизайне при эволюции системы).
Здравствуйте, thesz, Вы писали:
G>>Также любопытен подход CRC Cards — обязателен к изучению для любого проектировщика и архитектора. Это единственный подход, который позволяет описать объектную систему с высоты "птичьего полета" — пренебрегая несущественными деталями, и оставляя суть. Набор CRC-карт для вашей системы — это квинтэссенция ее дизайна. Это выше уровнем, чем модели UML и OMT. Мы ее применяли как для языка, описывающего дизайн на раннем этапе, так и как лучшее средство документирования кода (CRC-карты писались в коде в комментариях к основным классам — единственно возможный подход не потерять информацию о дизайне при эволюции системы).
T>They are soooo 80-sh: The name CRC comes from <b>Class</b>, Responsibilities, and Collaborators which the creators found to be the essential dimensions of object oriented modeling.
So what? They are still beautiful. And still, they actually are not bound to OO and classes, cause in reality they don't have any notion of "aggregation" and encapsulated state. You don't think in term of "state" operating with CRC cards, you think in term of functions and responsibilities. So, they can be perfectly used to describe purely functional system as well, no matter how they are decomposed. О чем вряд-ли думали Кент Бек и компания, когда делали свой доклад на OOPSLA.
Так бывает. Эта штука более обща чем ООП — это квинтэссенция дизайна. Я, к примеру, вчера с успехом описал при помощи CRC-карт дизайн функционально чистой подсистемы работы с временными рядами для Эрланга, и весьма доволен результатом — самому понятно стало.
Здравствуйте, geniepro, Вы писали:
G>Я вот тут подумал, а что если ввести в эту электронную таблицу логические операции && || и операции сравнения > < >= <= == /= ... Что это даст? Можно ли будет с их помощью вычислить такие вещи, фибоначчи, факториал. аккермана и простые числа? Ведь макросов нету, циклов нету, циклические ссылки отбраковываются... Как их вычислять-то в таких условиях? А как вычислить их в Экселе, не пользуясь макросами?
В Экселе так не принято. Там принято делать рекурентные формулы. Пример. Скажем, у нас есть список расходов, и надо добавить к нему колонку, где будет их сумма нарастающим итогом. Тогда делается так.
Name Price Total
a 10 =b2
b 6 =c2+b3
c 7 =c3+b4
и так далее. Формула в total ссылается на свой предыдущий результат в ячейке выше, и прибавляет к нему ячеку слева. Таким образом можно определить произвольную рекуррентную формулу.
Кроме того, в Экселе есть оператор IF, который на самом деле эквивалент condition ? then : else, где все три выражения — формулы. Кроме того, в Экселе есть функции, оперирующие диапазонами даных. Например SUM(range).
Короче говоря, настоящая сила Экселя состоит как раз в том, что в нем без программирования можно делать достаточно навороченные вещи, пользуясь только набором предопределенных операций. Скажем, в нем можно запросто вести бухалтерию, составить бизнес-план и провести анализ сценариев, или выполнить статистическую обработку данных. Эксель — пожалуй, единственное средство, которое позволяет с легкостью применять компьютер для вычислений не программистами — им с легкостью может пользоваться бухгалтер, финансист, секретарша, менеджмент, и прочие. Более того — я видел и достаточно сложные системы на Экселе — например, систему управления производством (правда — уже со скриптами на бейсике, которые производят рассчет нарядов и планирование).
Что касается применений в программировании — мы применяли Эксель для обработки и анализа данных замеров производительности профайлером, для планирования трудозатрат, для анализа метрик и составления отчетов. Короче, крутая штука Эксель.
Здравствуйте, Gaperton, Вы писали:
G>Короче говоря, настоящая сила Экселя состоит как раз в том, что в нем без программирования можно делать достаточно навороченные вещи, пользуясь только набором предопределенных операций. Скажем, в нем можно запросто вести бухалтерию, составить бизнес-план и провести анализ сценариев, или выполнить статистическую обработку данных. Эксель — пожалуй, единственное средство, которое позволяет с легкостью применять компьютер для вычислений не программистами — им с легкостью может пользоваться бухгалтер, финансист, секретарша, менеджмент, и прочие. Более того — я видел и достаточно сложные системы на Экселе — например, систему управления производством (правда — уже со скриптами на бейсике, которые производят рассчет нарядов и планирование).
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, Gaperton, Вы писали:
G>>Короче говоря, настоящая сила Экселя состоит как раз в том, что в нем без программирования можно делать достаточно навороченные вещи, пользуясь только набором предопределенных операций. Скажем, в нем можно запросто вести бухалтерию, составить бизнес-план и провести анализ сценариев, или выполнить статистическую обработку данных. Эксель — пожалуй, единственное средство, которое позволяет с легкостью применять компьютер для вычислений не программистами — им с легкостью может пользоваться бухгалтер, финансист, секретарша, менеджмент, и прочие. Более того — я видел и достаточно сложные системы на Экселе — например, систему управления производством (правда — уже со скриптами на бейсике, которые производят рассчет нарядов и планирование).
К>Электронные таблицы — сила, это факт, а вот на лямбде ещё вот такую примочку выложили к экселю.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
А не проще ли было как-то поимперативнее? Я хаскель знаю слабо, но вот в духе потока сознания родилось следующее:
import Control.Monad
import Data.Array.IO
import Data.IORef
import Data.List
import Data.Char
import Text.ParserCombinators.Parsec
import Control.Exception
import Prelude hiding (catch)
--------------------------------------------------------------------------------------data Table = Table
{ tWidth :: Int
, tHeight :: Int
, tData :: IOArray (Int,Int) Cell
}
data Cell = CEmpty
| CNumber Integer
| CText String
| CExpr Expr
| CError String
data Expr = ESimple Term
| EBinary Expr Op Term
data Term = ENumber Integer
| ERef Int Int
data Op = OPlus
| OMinus
| OMul
| ODiv
deriving Eq
numOps = [(OPlus, (+)), (OMinus, (-)), (OMul, (*)), (ODiv, div)]
evalOp (CNumber n1, op, CNumber n2) = CNumber $ n1 `f` n2 where Just (_,f) = find ((== op).fst) numOps
evalOp _ = errEval
errParse = CError "#Parse"
errEval = CError "#Eval"
errIdx = CError "#Index"
errExpr = CError "#Expr"-- unevaluatedinstance Show Cell where
show CEmpty = ""
show (CNumber n) = show n
show (CText t) = t
show (CExpr e) = show errExpr
show (CError e) = e
--------------------------------------------------------------------------------------
parseTable :: String -> IO Table
parseTable input = do
case lines input of
[] -> error"invalid input"
(l:ls) -> do let [h,w] = map toInt . split $ l
dat <- newArray ((0,0),(h-1,w-1)) CEmpty :: IO (IOArray (Int,Int) Cell)
forM_ (zip [0..] ls) $ \(i,l) ->
forM_ (zip [0..] $ split l) $ \(j,x) ->
writeArray dat (i,j) $ parseCell x
return Table { tWidth = w, tHeight = h, tData = dat }
where toInt = read :: String -> Int
split = lines . map (\c -> if c == '\t'then'\n'else c)
parseCell :: String -> Cell
parseCell "" = CEmpty
parseCell ('\'':s) = CText s
parseCell ('=' :s) = case parse expr "" s of
Right e -> CExpr e
Left _ -> errParse
parseCell s | all isDigit s = CNumber (read s)
| otherwise = errParse
expr = do { t <- term; rest $ ESimple t }
rest e = do { eof; return e }
<|> do { o <- op; t <- term; rest $ EBinary e o t }
op = foldl1 (<|>) $
map (\(ch,op) -> do { char ch; return op })
[('+',OPlus), ('-', OMinus), ('*', OMul), ('/', ODiv)]
term = do { n <- number; return $ ENumber n }
<|> do { a <- letter; n <- number; return $ ERef (fromIntegral n - 1) (ord (toUpper a) - ord 'A') }
number = do { ds <- many1 digit; return (read ds :: Integer) }
--------------------------------------------------------------------------------------
printTable :: Table -> IO ()
printTable (Table w h d) = do
a <- newArray ((0,0),(h-1,w-1)) "" :: IO (IOArray (Int,Int) String)
forM_ [(i,j) | i <- [0..h-1], j <- [0..w-1]] $ \(i,j) -> do
c <- readArray d (i,j)
t <- evaluate (show c) `catch` (const $ return $ show errEval)
writeArray a (i,j) t
maxw <- foldl (\a x -> a `max` length x) 1 `liftM` getElems a
forM_ [0..h-1] $ \i -> do
(putStrLn . concat . intersperse " " . map (pad maxw)) =<< (forM [0..w-1] $ \j -> readArray a (i,j))
where pad w s = s ++ replicate (w - length s) ' '--------------------------------------------------------------------------------------data CState = CInit | CEval | CDone deriving Eq
evalTable :: Table -> IO Table
evalTable (Table w h d) = do
st <- newArray ((0,0),(h-1,w-1)) CInit :: IO (IOArray (Int,Int) CState)
d' <- mapArray id d -- copy ("let d' = d" evaluates table in place)let eval ij = do
curst <- readArray st ij
case curst of
CDone -> return ()
CEval -> error"eval"
CInit -> do writeArray st ij CEval
c <- readArray d' ij
c' <- case c of
CExpr e -> evalExpr e
_ -> return c
writeArray d' ij c'
writeArray st ij CDone
evalExpr (ESimple t) = evalTerm t
evalExpr (EBinary e o t) = do e' <- evalExpr e
t' <- evalTerm t
return $ evalOp (e', o, t')
evalTerm (ENumber n) = return $ CNumber n
evalTerm (ERef i j) = if i < 0 || j < 0 || i >= h || j >= w
then return errIdx
else do
tmpst <- readArray st (i,j)
if tmpst == CEval
then return errEval
else do if tmpst == CInit then eval (i,j) else return ()
c' <- readArray d' (i,j)
case c' of
CNumber _ -> return c'
_ -> return errEval
forM_ [(i,j) | i <- [0..h-1], j <- [0..w-1]] eval
return $ Table w h d'
--------------------------------------------------------------------------------------
main = printTable =<< evalTable =<< parseTable =<< getContents
Наверное, если знать язык получше, можно упростить и сократить.
Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К, я тоже не выдержал. см. http://www.haskell.org/haskellwiki/Ru/Problem_K
А можешь на английский перевести текст задания? Почему-то мне захотелось поделиться со своими коллегами, сам боюсь переводить, шпрехаю плохо
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))
Re: [Haskell] Решение задачи К
От:
Аноним
Дата:
30.11.07 04:43
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:
BZ>поскольку каждый архитектор должен построить дом, подписать письмо четырёх и решить задачу К
Не будучи архитектором, все же решил для треннировки написать свой эксел. Сумбурный вариант можно найти здесь: Еще одно решение K на Haskell
Не уверен, "легально" ли я использовал Parsec, но писать свой монадный парсер не хотелось
Почему хаскель? Потому что сочетание ленивости, меморизации и монадных комбинаторов делают его, на мой взгляд, идеальным средством для данной конкретной задачи. Возможно я и ошибаюсь, но именно ленивость с меморизацией позволяет "автоматически" разрулить зависимости наиболее эффективным способом без всякой теории графов, а проверка цикличности ссылок с "протаскиванием" ошибок прозрачно и элементарно имплементируется при помощи комбинации StateT, ReaderT и ErrorT. Так что "вычислительная" часть получилась достаточно простой и компактной (код до the коментария).
Возможно кому-то это будет интересно и прошу прощение за отсутствие комментариев равно как и явно очерченного дизайна
