1. Haskell / Говнокод #12056

    −82

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    only :: (Integral nt) => nt -> [Bool]
    only n = [ x `mod` n == 0 | x <- [0..] ]
    
    each :: (Integral nt) => nt -> [a] -> [a]
    each n xs = [ snd x | x <- filter fst $ zip (only n) xs ]
    
    main = do print $ each 2 [1,2,3,4,5,6,7,8,9]

    Haskell. Получение каждого n-го элемента списка.

    Запостил: Fai, 05 Ноября 2012

    Комментарии (81) RSS

    • Интегралы мы ещё в школе проходили.
      Ответить
    • Я ждал этого. На самом деле действительно переодически приходится "теговать" элементы дополнительной информацией (хоть это и не тот случай, когда это необходимо), так вот тогда код становится некрасивый. Далеко не всегда можешь придумать, как от этого избавится.
      Ответить
      • Если под тегованием понимается (only :: (Integral nt) => nt -> [Bool]), то оно и тут необязательно.

        Если нет, прошу пояснить.
        Ответить
        • превращение списка [xi] в [(xi, tagi)]
          Ответить
          • Здорово. Как правильно было замечено, именно в этом и была проблема.
            Ответить
    • http://ideone.com/RILglX

      a = [1..50]
      b = [1..]
       
      aion [] ld = ld
      aion ls ld = (head ls) : ld
       
      skipEachN _ [] = []
      skipEachN n l = aion dl $ skipEachN n dl
              where dl = drop n l
       
      main = do 
              print $ skipEachN 5 a
              print $ take 10 $ skipEachN 5 b
      Ответить
      • each n = unfoldr $ \xs -> do (x:_) <- Just xs; Just (x, drop n xs)
        Ответить
      • Код хороший, только вот делает не совсем то, что первоначальный.
        Ответить
        • >Код хороший, только вот делает не совсем то, что первоначальный.
          Ниже исправил это кощунство:
          http://govnokod.ru/12056#comment158782
          Ответить
    • >Получение каждого n-го элемента списка.
      Лол, что ты написал? Почему у тебя первый элемент списка считается энным?
      http://ideone.com/2GtgDK
      Ответить
      • > первый элемент списка
        кэп намекает, что в списках хаскеля индексирование принято с 0
        Ответить
        • Оки, уговорил:
          http://ideone.com/YpEGDB
          a = [1..50]
          b = [1..]
           
          aion [] ld = ld
          aion ls ld = (head ls) : ld
           
          skipEachN _ [] = []
          skipEachN n l = aion l $ skipEachN n dl
                  where dl = drop n l
           
          main = do 
                  print $ skipEachN 4 a
                  print $ take 10 $ skipEachN 4 b
          Ответить
          • > aion ls ld = (head ls) : ld
            почему не
            aion (x:_) ld = x : ld
            Где хвалёные навыки паттерн-матчинга
            Ответить
          • Чутка улучшил:
            each _ [] = []
            each n (x:xs) = x: (each n $ drop (n - 1) xs)


            Нормально?
            Ответить
            • Пока это самый лучший и очевидный вариант :)
              Ответить
              • есть еще sieve http://hackage.haskell.org/packages/archive/utility-ht/latest/doc/html/Data-List-HT.html#g:5
                Ответить
            • http://ideone.com/R9KFE1
              Ага, годнота.
              Ответить
              • Только сигнатуру функции добавь, а то ошибка:
                http://ideone.com/bjbH3A
                Ответить
                • Хм. А в чём причина? Хочу разобраться.

                  upd: вижу. Он не может узнать, что за тип у списка при передаче пустого.
                  Ответить
                • Стоп.
                  each :: Int -> [a] -> [a] - не работает!

                  Получается нужно явно указывать тип "a" или при использовании писать (each 1 []) :: Type.

                  Криво.
                  Ответить
                  • each :: (Show a, Integral n) => n -> [a] -> [a]
                    Должно быть как-то так, но это не правильно скорее всего, поэтому ждем какого-нибудь Хацкелиста.
                    Ответить
                    • Все-равно не работает:
                      http://ideone.com/4vi9eJ
                      Ответить
                  • Дополнительные аннотации типа не нужны, Show тем более. Проблема глубже: даже
                    main = print []
                    не работает, т.к. print вызывает полиморфную функцию show, а для пустого списка непонятно, что вызывать. Поэтому нужно явно указывать тип пустого списка.
                    На самом деле, это не такая уж большая проблема, т.к. явно передавать пустой список мало кому нужно: обычно они возникают в процессе обработки, и его "тип" известен.
                    Ответить
      • >> Почему у тебя первый элемент списка считается энным?
        > в списках хаскеля индексирование принято с 0

        Именно.
        Ответить
        • Ты так говоришь, как будто 0 это степень n.
          Ответить
          • Грубо говоря берутся все элементы, индексы которых делятся на n.

            А т.к. 0 делится на n* априори, берётся и он.

            * Исключая n = 0
            Ответить
    • Можно ещё как-то так:
      skipEachN n l = zipWith (!!) l [0, n - 1 ..]

      Только что-то не компилится тоже:
      http://ideone.com/lyFejA
      Ответить
      • Вот так работает:
        each n xs = [ xs!!i | i <- [0, n .. len xs - 1] ]
        Ответить
        • А нет. Может вылететь, если список очень маленький.
          Ответить
      • !!!
        each n xs = zipWith (!!) (repeat xs) [0, n.. len xs - 1]

        Проблема была в том, что оператор !! применим только как (массив!!индекс), а он применялся как (значение_массива!!индекс).

        Так что приходится делать repeat(xs) для получения списка. Но есть вариант получше:
        http://ideone.com/Sc3KOY

        Вот он чемпион читабельности!
        Ответить
        • Есть минус - не работает с бесконечными списками.
          Ответить
        • >(repeat xs)
          Эка я протупил.

          >Вот он чемпион читабельности!
          И вот и ты уже не спишь... Хаскель не нужен)))
          Только есть одна проблема. Этот чемпион не может в бесконечные списки, так что не вариант. Подозреваю, что и производительность из-за !! оставляет желать лучшего.
          Ответить
    • Подводя итоги скажу, что проблема изначально была в попытке представить эту функцию операциями над списком значений, хотя необходимо было работать с индексами.
      Ответить
    • Они нашли друг друга!
      Ответить
    • each _ [] = []
      each n (x:xs) = x: (each n $ drop (n - 1) xs)

      Пока это самый очевидный и самый правильный вариант, если сигнатурку типов поправить
      Ответить
      • Есть ещё вариация:
        each _ [] = []
        each n xs@(x:_) = x: each n (drop n xs)


        Немного короче, более понятная в правой части и менее понятная в левой. Хотя кому-как.
        Ответить
        • each _ [] = []
          each n xs@(x:_) = x: each n $ drop n xs
          Ответить
          • Тогда нужно
            each n xs@(x:_) = x: (each n $ drop n xs)
            Ответить
            • each n xs@(x:_) = (x:) $ each n $ drop n xs
              Ага, не стало лучше...
              Ответить
              • Можно и так:
                each n xs = head xs: each n (drop n xs)

                С одной стороны читается лучше и запись короче, с другой стороны обосрут же если первый элемент через head получать, а не через патерн-матчинг.

                upd: Кстати, есть мыло, аська, скайп для вопросов по ФП? Говнокод всё-таки не для этого.
                Ответить
      • > если сигнатурку типов поправить

        Я уже выяснил, что можно не править. Проблема всё-таки в функции print которая не знает как вывести пустой список.

        main = print [] -- Ошибка
        Ответить
        • > Если сделать так:
          Костыль же вроде?

          upd: Хотя наверное ты прав.
          upd2:Ты обновил пост. Инфа не актуальна.
          Ответить
          • Поправил уже. Так всё-равно не работало :(
            Ответить
    • (Здесь должен был быть пост про удобство питона, где достаточно написать lst[::n], но мне неохота холиварить.)
      Ответить
      • А на HQ9+N это записывается в один символ!
        Ответить
      • (Здесь должно быть замечание о том, что each ленив и может работать с бесконечными списками, но мне неохота холиварить)
        Ответить
        • Ну вообще в питоне есть itertools.islice(), но оно вроде как с ограничениями (не гарантируется работа с входной последовательностью длиннее чем sys.maxint элементов).
          Если надо больше, то придется делать всё самому.
          Ответить
          • И список тоже?
            Ответить
            • ну бесконечных списков в питоне нет. Хотя есть бесконечные последовательности, по которым можно итерироваться хоть до посинения. А вот фильтр, пропускающий наружу каждый n-й элемент такой последовательности - наверно придется делать самому.
              Ответить
              • Мне тоже нравится елда. Жаль, что они не написали достаточно готовых алгоритмов для неё. В F#\OCaml этим не поскупились. Модуль Seq содержит все необходимое.
                Ответить
        • >each может работать с бесконечными списками
          Эти сказки можно рассказывать только ньюфагам, чтобы затащить в функциональщину.

          На деле список очень даже конечный. Притом предсказть конец бесконечного списка весьма не просто. Ты никогда не можешь быть уверен наверняка, что для обработи данной задачи тебе хватит объёмов памяти.
          Ответить
          • > предсказть конец бесконечного списка
            head $ reverse [1..]
            Ответить
          • > Притом предсказть конец бесконечного списка весьма не просто.
            А зачем? Все равно ты не будешь использовать весь этот список, а возьмешь для вывода\сохранения только нужную его часть.

            На самом деле бесконечный список довольно удобная абстракция, сокращающая код - не надо писать отдельный случай для пустого списка. Я так писал Метод Наименьших Квадратов, который строит бесконечные вектора и матрицы, сводит к треугольному виду бесконечную систему уравнений, и выводит ответ нужной размерности... Если интересно - могу выложить.
            Ответить
            • Как связаны бесконечные списки и случай пустого списка?
              Ответить
              • Если мы работаем с конечным списком, то приходится писать так:
                map _ [] = []
                map f (x:xs) = f x : map f xs

                Если же список бесконечен - то код упрощается:
                map f (x:xs) = f x : map f xs
                Ответить
                • И надо еще сделать будет, что пустой список - бесконечный список из undefined.
                  Ответить
                  • Поясни?
                    Ответить
                    • -- Бесконечный список - это бесконечный список
                      endlesList = [1,2..] 
                      
                      -- Пустой список - это бесконечный список жоп (_|_)
                      emptyList = cycle [undefined]
                      
                      -- Конечный список - это бесконечный список с началом из 
                      -- определенных значений и окончанием из бесконечного списка жоп 
                      finiteList = [1,2,3] ++ emptyList
                      Ответить
                      • Зачем такое? Ты же перевернуть список не сможешь.
                        Ответить
                        • Это в гипотетическом языке, где все есть бесконечный список.
                          Ответить
                          • А как перевернуть бесконечный список?
                            Ответить
                            • 1)Пройти по списку рекурсивно до первой жопы, сохраняя в стеке значения.
                              2)Разворачивать стек, создавая новый конечный список, который в конце тоже дополнится жопами.
                              3) ...
                              4)PROFIT

                              Одна проблема: Когда мы создали первый [1], то он уже превращается в 1ницу с бесконечножопным хвостом, так что добавить следующий элемент списка уже не представляется возможным.

                              Ну и как бы вообще совершенно не понятна идея этой бесполезной бесконечножопной фичи
                              Ответить
            • Вот говори что хочешь, а мне елды не хватает (бесконечные последовательности) в Хаскеле
              Ответить
              • > мне елды не хватает
                А зачем она в языке с повсеместной ленивостью?
                Ответить
                • Чтобы память не забивать бесконечной ерундой, если нужен однопроходный бесконечный список.
                  Ответить
                  • Можно подумать, что в хаскеле бесконечный список забивает память. Не держи его за хвост, и gc будет пожирать ненужные его части.
                    Ответить
                    • А ведь ты гений! Только вот написал ты чуть выше по коду let a=[1..] и лексически захваченная константа держит список за хвост. Что делать? Не пользоваться let для списков? Но это же не читаемо.
                      Ответить
                      • Как вариант - where/let внутри самой функции.
                        Ответить
                        • >Как вариант
                          MRef на список? - мутабильное говно.
                          Ещё варианты?
                          Ответить
                          • > Как вариант - where/let внутри самой функции.
                            f x = let a = [1..] in ...

                            Вот тут a никто не держит кроме выражения, которое будет стоять на месте точек. Сборщик мусора отлично будет поедать этот список.
                            Ответить

    Добавить комментарий