1. Куча / Говнокод #17300

    +131

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    next_int() ->
      receive {next_int, N} -> 
        self() ! {next_int, N + 1}, 
        N
      after 0 ->
        self() ! {next_int, 0}, 
        0
      end.
    
    ...
    [{A, next_int()}|| A <- SomeList]

    Простейший способ пронумеровать элементы списка эрланге. Найдено в продакшне, ошибки сохранены.

    Запостил: lesmugfrog, 12 Декабря 2014

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

    • add_numbers(List) ->
          Numbers = lists:seq(0, length(List) - 1),
          lists:zip(List, Numbers).
      Я не спец по эрлангу, но наверное как-то так?
      Ответить
      • неленивая чистота смотрится так убого...
        zip [0..] xs
        Ответить
      • enumerate([X | Xs]) ->
            lists:reverse(
              lists:foldl(fun(A, B) ->
                                  [{_, N} | _] = B,
                                  [{A, N + 1} | B]
                          end,
                          [{X, 0}], Xs)).

        За два прохода.

        enumerate_rec(List) ->
            Enum = fun(Acc, N, Func) -> 
                           case Acc of
                               [X | Xs] -> [{X, N} | Func(Xs, N + 1, Func)];
                               [] -> []
                           end
                   end,
            Enum(List, 0, Enum).

        За один проход, но без хвостовой рекурсии.

        Вобщем, хорошего способа по-настоящему чет не наблюдается.
        Ответить
        • Ну вот с хвостовой (реверс, вроде как, читерски быстр и написан на сях):
          enumerate(List) ->  lists:reverse(enumerate(List, [], 0)).
          enumerate([], Acc, _) -> Acc;
          enumerate([X|Rest], Acc, N) -> enumerate(Rest, [{X, N}|Acc], N+1).
          Ответить
          • Так в обратную ж сторону...
            Ответить
            • Почему? Слева-направо обходит и нумерует.

              http://ideone.com/1crYjm
              Ответить
              • Я про изначальный вариант, а не с реверсом.

                Ну мой первый вариант тоже с реверсом тогда такой же.

                А вообще, я тут подумал, без частично инстанциированых типов данных (альтернатива присваиванию), или нарушения всех трех принципов субструктурной системы типов (обмен, послабление и упрощение) невозможно генерировать список в направлении от начала к концу. Я думаю, что если напрячься, то это како-то формально можно выразить.
                Ответить
                • А изначальный вариант тоже по порядку нумерует - отправляет себе {next_int, 0} и возвращает 0, затем, получив {next_int, N} отправляет себе {next_int, N+1} и возвращает N. Из-за этого там косяк - два нуля в начале последовательности.

                  > невозможно генерировать список в направлении от начала к концу
                  Вроде бы. Не от хорошей же жизни в эрланге всё через хвостовую рекурсию и lists:reverse() пишут.

                  > формально можно выразить
                  Ну совсем не формально, но как-то так: мы можем прицепить элемент в начало списка (тем самым строя его с конца); мы можем добавить элемент в конец, скопировав весь список (медленно); мы можем забуферизовать элементы на стеке (не хвостовая рекурсия) и мы можем забуферизовать их в списке (хвостовая рекурсия + reverse). Вроде бы других вариантов тупо нет.
                  Ответить
                  • Нет, я про изначальный вариант в
                    http://govnokod.ru/17300#comment259145

                    Он же мне на почту приходит :)
                    Ответить
                    • А, ясно. Поэтому я стараюсь не доверять сообщениям в почте и на стоке, т.к. они отстают от реальной версии.
                      Ответить
                  • > Вроде бы других вариантов тупо нет.
                    Вернее они есть, но они сводятся к буферизации элементов в том или ином виде.

                    Всё печально. lists:reverse/1 неизбежен.

                    P.S. Радует только то, что джва прохода это всё еще O(n), просто с большей константой, и то, что lists:reverse/1 достаточно шустрый, чтобы не увеличить эту константу вдвое.
                    Ответить
        • > foldl
          Кстати, а foldr в эрланге поди сначала переворачивает список, а потом отдаёт его foldl'у?
          Ответить
          • А может быть и нет. Как-то ж в Эрланге генераторы работают - а там ведь тоже нужно строить от начала к концу. Наверное есть какая-нибудь уловка вне доступа средств самого языка. Хотя ман говорит foldl/3 is tail recursive and would usually be preferred to foldr/3. Что наталкивает на мысль, что может быть и нет :/
            Ответить
            • > генераторы
              В теории можно сделать на сях - никто не увидит узлы пока генератор не вернул результат, поэтому можно внаглую добавлять новые в конец. В реализации map'а можно поступить аналогично.

              P.S. Но это может нарушить временные характеристики - емнип, тред нельзя прервать, пока он исполняет bif.
              Ответить
    • >Erlang
      >Production
      ЩИТО
      Ответить
      • А щито не так? Это язык для продакшена и только для продакшена. Что-то другое на нём писать никто не решится.
        Ответить

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