Ilya
а насчёт планшетов - сейчас у многих планшеты с чехлом-клавиатурой
Ilya
почти что ноутбук и есть
Quet
@voidlizard ты просто наверное не понимаешь какая тут "работа" у людей происходит
это у тебя там веб-сервис опердень и генерация сишечки
а тут народ выясняет какой тип у (.) (.) (.) и почему такой
Quet
для второго варианта телеграм бот -- годится ок
Влод
короче не знаю о чём там разговор, но бот для тг это задача примерно на день, а портировать гхц на андроид это задача на неопределнное время. хотя мб кому-то наоборот подогреет интерес.
Serghei
итак, решил я это дело доковырять с монетками разменными. на степике предпологается что для для монеты 7 и номилов 2, 3, 7 должен быть ответ [[2,2,3],[2,3,2],[3,2,2],[7]] что не до конца приминимо в жизни. хотя я конечно решил
потом я подумал что не плохо бы показать только уникальные варианты. 223 и 322 не уникальны
у меня получилось
import Data.List
calc :: Int -> [Int] -> [[Int]]
calc 0 _ = [[]]
calc _ [] = [[]]
calc amount coins = nub $ map sort [c:cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]
догадываюсь что из-за моего опыта я написал лапшекод :)
но вопрос в другом, если я хочу получить ответ на вопрос "сколько всего вариантов", то после переделки в
import Data.List
calc :: Int -> [Int] -> Int
calc 0 _ = 0
calc _ [] =
calc amount coins = length $ nub $ map sort [c:cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]
я получаю
• Couldn't match expected type ‘[[Int]]’ with actual type ‘Int’
• In the expression: calc (amount - c) coins
In a stmt of a list comprehension: cs <- calc (amount - c) coins
In the second argument of ‘map’, namely
‘[c : cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]’
Serghei
я не уловил суть? :(
Serghei
> calc _ [] =
calc _ [] = 0
Serghei
да, понял где ошибся 😔
Ilya
итак, решил я это дело доковырять с монетками разменными. на степике предпологается что для для монеты 7 и номилов 2, 3, 7 должен быть ответ [[2,2,3],[2,3,2],[3,2,2],[7]] что не до конца приминимо в жизни. хотя я конечно решил
потом я подумал что не плохо бы показать только уникальные варианты. 223 и 322 не уникальны
у меня получилось
import Data.List
calc :: Int -> [Int] -> [[Int]]
calc 0 _ = [[]]
calc _ [] = [[]]
calc amount coins = nub $ map sort [c:cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]
догадываюсь что из-за моего опыта я написал лапшекод :)
но вопрос в другом, если я хочу получить ответ на вопрос "сколько всего вариантов", то после переделки в
import Data.List
calc :: Int -> [Int] -> Int
calc 0 _ = 0
calc _ [] =
calc amount coins = length $ nub $ map sort [c:cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]
я получаю
• Couldn't match expected type ‘[[Int]]’ with actual type ‘Int’
• In the expression: calc (amount - c) coins
In a stmt of a list comprehension: cs <- calc (amount - c) coins
In the second argument of ‘map’, namely
‘[c : cs | c <- coins, amount >= c, cs <- calc (amount - c) coins]’
nub, sort и прочие пряники в таких чисто "олимпиадных" задачах не применяют. Постараюсь объяснить.
К sort стоит обращаться, если у тебя откуда-то уже есть список, и тебе надо его упорядочить (спасибо, кэп).
А если ты сам конструируешь список "с нуля", то упорядоченность ответа просто должна быть зашита в алгоритм. Это будет и эффективнее, и красивее. Зачем сортировать элементы, если можно сразу расставлять правильно?
Аналогично с nub. Если твой алгоритм выбрасывает кучу результатов, которые ты считаешь одинаковыми, то не нужно в конце фильтровать ответ nub-ом. Вместо этого переделай алгоритм так, чтобы одинаковые результаты не получались.
Ну такая "гигиена" решения подобных задач приходит с опытом, вряд ли тут можно выделить какое-то общее правило...
Ilya
Вот что у меня получилось
Ilya
calc 0 _ = [[]]
calc _ [] = []
calc amount (c:cs) = calc amount cs ++ if amount < c then [] else map (c:) $ calc (amount - c) (c:cs)
Ilya
особо не тестил, но вроде работает
Ilya
А вообще твоя задача похожа на классическую https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0
Serghei
хм
Serghei
любопытно
Нурлан
А вообще твоя задача похожа на классическую https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0
Классическая и есть, толь с модификацией. Где-то в загашниках у меня оставалось формула для неё с алгоритмом линейной сложности.
Нурлан
calc 0 _ = [[]]
calc _ [] = []
calc amount (c:cs) = calc amount cs ++ if amount < c then [] else map (c:) $ calc (amount - c) (c:cs)
Здесь проблема при тестировании чисел больших 100 начнётся.
Нурлан
Может тест не пойти, если это олимпиада
Ilya
ну я в ++ конечно тоже не уверен =)
Ilya
нехорошая операция...
Нурлан
Но я тогда на эту формулу три дня убил.
Serghei
это не олимпиада. просто попалась задачка, человек говорит что она давалась на какой-то там олимпиаде (когда-то там), по этому я сказал "говорят олимпиадная". но у меня никакой олимпиады понятное дело нет. второй день ковыряю всякое разное на хаскеле, пока выходные - тренируюсь )
Serghei
ну и да, тут скидывали ссылку на степик- там похожая задача
Нурлан
та задача которую я решал это разбиение числа n на k слагаемых
Нурлан
у тебя чуть иначе задача стоит, как я понял разбиение числа n по заданным слагаемым
Нурлан
смотрю я на свой старый код... повеситься хочется 😂
Alexander
что скажете про хаскельбук? кстати не думаю что вы тратили 60$ :)
Я тратил, норм книга, автор мудак, но книга хорошая
Alexander
Мне лень перечитывать 300 сообщений, если там что-то интересное или вопросы были - пните
Anonymous
Есть какая-нибудь обязательная к прочтению книга по теории типов?
Dmitry
обязательного нет ничего, а так - TAPL
Anonymous
Спасибо!
Anonymous
Есть какая-нибудь обязательная к прочтению книга по теории типов?
https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/
Anonymous
Есть какая-нибудь обязательная к прочтению книга по теории типов?
https://homotopytypetheory.org/book/ - 1 глава
Anonymous
Спасибо всем огромное
Anonymous
Вопрос к пользователям emacs-а (чистого гнушного, 24.5.1, без иксов). У меня в ghc-mod... как бы сказать... большая задержка между нажатием клавиши и ответом редактора. С чем может быть связано? Чинится ли? Отключение ghc-mod'а помогает.
Dmitry
с емаксом время от времени так. я когда на окамле писал, у меня тормозил модуль подсветки окамла, пришлось вернуться в вим
Anonymous
Мне некуда возвращаться. Я поищу ещё решение, если найду, то напишу.
Влод
> гомотопическая теория типов.
Конечно же это обязательная книга. Каждый хаскелист на зубок знает
Anonymous
> гомотопическая теория типов.
Конечно же это обязательная книга. Каждый хаскелист на зубок знает
Там 1 глава совсем не про это.
Alexander
@quetzal (сорри что оффтоп), а что get NEXT_DUP делает если значения закончились?
Alexander
впрос снят
Alexander
путать true и false плохо :(
Evgeniy
https://wiki.haskell.org/Heterogenous_collections
вот кстати интересно спросить по поводу Hlist-ов в хаскелле - в скале в наиболее популярной реализации (http://jto.github.io/articles/getting-started-with-shapeless/), количество элементов в списке сильно аффектит время компиляции - а как тут ситуация?
Dmitry
тут сервантовское API с большим количеством эндпойнтов может уронить ghc
Dmitry
не помню, может даже по исчерпанию памяти
Quet
это на каком количестве эндпоинтов такое?
Dmitry
тут вообще должны быть непосредственные наблюдатели этого явления, но что-то в районе сотни - другой, кажется
Misha
а вот кстати интересно как оно там внутри устроено и насколько эффективный там роутинг для большого количества эндпоинтов
Misha
не думаю, что они там суффиксное дерево на типах написали или типа того
Misha
хотя вдруг и написали, конечно
Dmitry
префиксное
Dmitry
написали
Misha
круто
Dmitry
не знаю в какой версии оно появилось, но несколько месяцев или с полгода как было объявление. по моему уже в "продакшоне"
Misha
https://github.com/haskell-servant/servant-benchmarks/blob/master/benchmarks/Routes.hs
Misha
как раз сто ендпоинтов
Misha
не падает наверное
Quet
https://github.com/haskell-servant/servant-benchmarks/blob/master/benchmarks/Routes.hs
от типов вытекли глаза
Dmitry
но вообще видится здравой идея пилить все на микросервисы, число эндпойнтов в которых не вылазит за сотню
Misha
хотя вырожденный случай
Quet
Misha
а как решать задачу с апдейтами "по узлам" в таких микросервисах? если у меня есть 10 микросервисов, какие-то из общаются сервантом по http друг с другом, то понятно, мне удобнее type Api = ... держать общим для каждой пары клиент/сервер. Но как тогда апдейтить клиента/сервера и не ломать API? В обычной ситуации спасает как раз нестрогость и то, что это json, а как быть с сервантом?
Misha
"то, что это json" = "любой текстовый формат, позволяющий пропускать поля"
Dmitry
фиг знает, поставить перед ними nginx, сет нод поднять на других портах ,передернуть nginx, старые ноды загасить
Dmitry
назвать модным словом "оркестрация"
Misha
immutable infrastructure, да
Dmitry
можно еще более наркомански
Dmitry
все эти ноды форкаются одним жирным процессом
Dmitry
который гасим и поднимаем новую версию
Dmitry
впрочем, не исключено что systemd предлагает что уже готовое для этой задачи
Misha
можно, но тогда весь кластер ляжет на некоторое время
Misha
а надо-то чтоб без даунтайма
Misha
иначе нафига микросервисы городить
Dmitry
что бы ghc не валился и не тормозил слишком сильно на компиляции серванта же
Misha
хм
Misha
ну разве что
Dmitry
ну т.е проблема согласованного апдейта и поддержания консистентности наверняка касается не только серванта
Dmitry
и для её решения есть же какие-то стратегии в зависимости от требований