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

    +133

    1. 1
    2. 2
    3. 3
    fib 1 = 1
    fib 2 = 1
    fib n = fib(n-1) + fib (n-2)

    Хаскель это вам не математика, тут надо и вычислительную сложность учитывать.

    Запостил: kipar, 27 Июня 2011

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

    • если использовать мемоизацию, то это будет не так плохо ...
      да и пример учебный
      Ответить
      • До мемоизации я еще не дочитал, но когда в туториале критикуют стандартные языки что мол в них факториал неочевидно (через цикл) приходится писать, и тут же такой пример на хаскеле, то это бред. На хаскеле тогда Фибоначчи еще более неочевидно будет.
        Ответить
        • сомнительный туториал, формула Стирлинга-Муавра же!
          Ответить
          • БЛДЖ!!!ФОРМУЛАСТИРЛИНГАМУВРАКОРНИИФЛОАТЫ ТРИСТРОКИ!!!
            надо {{0,1},{1,1}} возвести в степень n за логарифм и умножить на {1,1}
            Ответить
        • хорошо везде сохранять декларативный смысл...
          (и плохо если это сделано в ущерб производительности)
          Ответить
    • Да на Хаскелле все примеры из серии "смарите посоны какой красивый код сортировки/фибоначчи", а когда доходит до дела, то вместо этого красивого кода пишут какое-то жуткое говно на монадах и мутабельных переменных, которое ваще не читается, даже сраная сишка лучше читается, чем хаскеллоговно на монадах, короче говно говно говно.
      Ответить
      • >и мутабельных переменных
        Может иммутабильные переменные? В функциональных языках приняты не мутабильные переменные.
        Ответить
        • По умолчанию - да, все переменные НЕ мутабельные. Но когда нужны мутабельные, то в Хаскелле это пишется как полный пиздец.
          Ответить
          • >Но когда нужны мутабельные
            Чаще всего они и не нужны. Обычно, если умеешь нормально писать программы, то на 200 строк кода ~ 1 переменная, а остальные константы. Так что проблем то и нет.
            Ответить
      • Пахвально, ТарасИ решил выучить что-то кроме дельфи. ^_^

        Посмотри в сторону F#. На мой взгляд, читаемый паскаля-синтаксис в функциональном языке. И никаких тебе монад. Можно даже императивно писать.
        Ответить
        • Да просто взять любой сраный императивный язык, и сказать, что любая переменная по умолчанию - неизменяемая. Хочешь изменяемую - помечай её словом мутаблЭ. И любая функция по умолчанию не имеет права обращаться ни к чему, кроме параметров. Надо, чтобы обращалась - помечай её словом диртУ.
          И всё, язык сам провоцирует на чистый стиль.
          Ответить
          • >помечай её словом диртУ
            Можно на оригинальном языке?
            Ответить
            • dirty
              Ответить
              • Идея интересная. Из какого это языка?
                Ответить
                • Нет такого вроде. В Аде была попытка отделить процедуры (то, что что-то делает, может принимать in-out параметры) и функции (то, что возвращает значение, то есть out-параметры идеологически неверны и потому запрещены). Правда толку никакого от этого, ведь смотреть наружу из этих функций не запрещено, да и из-за отсутствия множественного присваивания народ костылит с передачей указателей. Поэтому скоро out-параметры в функциях разрешат.
                  Ещё я бы отделил dusty- просто грязные функции (которые смотрят снаружи себя, например, GetTime) и dirty- ОЧЕНЬ грязные функции (которые меняют состояние снаружи себя, например, Random). Разница в том, например, что заставить отладчик посмотреть значение dusty-функции ещё можно, а значение dirty-функции - почти невозможно, ведь всё нарушится.
                  Любая функция из внешней библиотеки объявляется как очень грязная, само собой. Но с возможностью через хаки заставить компилятор понимать её, как чистую.
                  Ну и понятно, что чистая функция может вызывать только чистые, dusty - чистые и dusty, а dirty - любые.
                  Ответить
          • Я бы ещё добавил ключевое слово shared.
            Нужно сделать, что-бы по умолчанию все static переменные (такие, что в С++) или глобальные переменные создавались по экземпляру на поток. Тогда проблем с синхронизацией между потоками не будет, не смотря на императивный стиль. А если хочешь погемороиться, то добавляешь ключевое слово shared к объявлению переменной и получаешь что хотел - одна переменная на все потоки.
            Ответить
            • Короче, идея в том, что по умолчанию все сущности предельно ограничены, а если хочешь добавить им новое свойство, которое может привести к ненужным зависимостям, но коророе тебе позарез нужно - отдельно это указывай.
              Ответить
              • Полностью согласен. Этого явно не хватает, особенно в современных мейнстрим-языках.

                Хуже того в современных C#\Java даже нельзя некоторые вещи ограничить, как например в С++. Например, в этих языках, даже нельзя указать, что-бы какие-то переменные были константными.
                Особенно это плохо с параметрами, передаваемыми в функцию.
                Передаёшь свой объект в функцию программиста из соседнего отдела. А эта функция твой объект безнаказанно портит, не предупреждая об этом во время компиляции!
                Ответить
                • > Особенно это плохо с параметрами, передаваемыми в функцию.

                  То есть модификатора const на входные параметры нету?
                  В Дельфи он есть, но он не мешает испортить содержимое динмассива (ссылочный тип потому что). То есть действует только на POD-типы.
                  В Аде он есть (только слово не const, а in), динмассивы портить нельзя (хитрые объекты - можно, но только если их составить определённым образом, "с дырой", так вот даже стандартный вектор был немного переделан так, чтобы убрать для него "дырку"), вешается на параметры по-умолчанию. Но с этим тоже есть косяк - вот например, я хочу скопировать объект и испортить копию. Всё нормально, но если объект был собран на стеке, то нафига его копировать, он и так снаружи сразу же забудется? Говорят, правда, что это есть такая оптимизация у компилятора, чтобы это разруливать.
                  Ответить
                  • >Всё нормально, но если объект был собран на стеке, то нафига его копировать
                    Например, код С++:
                    TConcreteObject o;//Собираем объект на стеке.
                    Function1(o);//Функция иногда изменяет объект, а я то не знал. 
                    Function2(o);//Объект иногда изменён\испорчен и функция принимает неверный параметр и эта ошибка иногда вылазит в рантайме.
                    Что-бы быть уверенным что функция не испортит объект - нужно писсимизировать код, создавая копию объекта
                    Function1(TConcreteObject(o));
                    Ответить
                    • Ну вот только остаётся надежда на то, что умный компилятор уберёт лишнюю пессимизацию.
                      Ответить
                    • >Например, код С++:
                      Тфу. На сишарп\ява конечно же.
                      В С++ эта проблема не стоит, тк там можно параметры при передачи в функцию делать константными:
                      void Function1(const TConcreteObject& o){



                      зы:фикс для второго кода из поста:
                      Function1(new TConcreteObject(o));
                      Ну и естественно TConcreteObject o инициализировать нужно.
                      Ответить
                  • В С++ можно гарантированно запретить изменения любых объектов\массивов по любым ссылкам и указателям (хоть ссылка на указатель на указатель и тд и все immutable). Правда, есть специальное ключевое слово mutable, которое позволяет при проектировании объекта разрешить изменять отдельные поля объекта.

                    Ну и const_cast никто не отменял, хотя это уже на совести пользователя.
                    Ответить
                    • Ну вот если у объекта есть метод, которые меняет данные по указателю, и ты передаёшь этот объект как константный параметр в некоторую функцию. То этой функции запрещено будет вызывать этот метод?

                      В Аде, например, это решается так: все указатели объекта приватны, все методы, что меняют данные по указателю, объявляются, как меняющие состояние объекта. Но это получается целиком на совести того, что пишет класс этого объекта.
                      Ответить
                      • >То этой функции запрещено будет вызывать этот метод?
                        Да, запрещенно. Можно вызывать только const методы
                        void TObj.method() const
                        {...};
                        Естественно, этот метод изменять члены объекта не может.
                        Ответить
                      • >ты передаёшь этот объект как константный параметр в некоторую функцию
                        Ну для указателей в С++ можно конкретно указывать что там константное, а что нет, например:
                        const TObject* const//нельзя менять ни объект ни указатель
                        const TObject* //Можно менять указатель, но не объект
                        TObject* const//Можно менять только объект, но не указатель
                        //Могут быть и более сложные ситуации:
                        const TObject* const * const& //константная ссылка на константный указатель на константный указатель на константный объект. ссылки всегда константны
                        Ответить
                        • А что-нибудь мешает в const TObject* const методе изменить то, на что указывает какое-нибудь внутреннее поле-указатель? Или это на совести того, кто пишет класс?
                          Ответить
                          • Если это указатель на собственное поле объекта, то компилятор заругается, а иначе зачем?
                            Если указатель указывает на внешний объект, то это забота внешнего объекта быть константным или нет.
                            Если внешний объект константный, то его без хаков будет не поменять.
                            Ответить
                            • Указатель на внешний объект, конечно же. Но именно значение этого внешнего объекта считается состоянием нашего объекта.
                              Например - класс строки. Сами символы лежат где-то по указателю, в поле не хранятся, есть только поле для указателя на них. Они для нашего класса - внешний объект. Но если их менять в const методе, то будет лажа. То есть это на совести разработчика класса.
                              Ответить
                              • >это на совести разработчика класса
                                Да...
                                Ответить
                  • >Всё нормально, но если объект был собран на стеке, то нафига его копировать, он и так снаружи сразу же забудется?

                    Видимо, имелась ввиду ситуация типа:
                    TClass fun(TClass o)
                    {
                      return f(o);//Тут что-нить посложнее, но не важно. При вызове этой функции просто создается измененная копия объекта o.
                    }
                    //...
                    TClass o;
                    TClass a = fun(fun(o));//После первого вызова fun создаётся копия объекта o, которую при втором вызове fun можно смело портить! Да, и такая оптимизация в новом стандарте С++\0x есть.
                    Сейчас покажу эту оптимизацию. Жаль что она ручками делается, хотя вроде какие-то упрощённые её варианты делают и компиляторы.
                    Ответить
                    • Ну или это, например, да. Ну или если там не класс o, а структура. И ты пишешь fun({x=1;y=2;z=3;w=smth_else}); То есть структура собирается на стеке, её спокойно можно менять.
                      Ответить
                      • Согласен, этот объект на стеке тоже можно безнаказанно менять, не смотря на константность:
                        fun(TClass(...));
                        Ответить
                        • >Сейчас покажу эту оптимизацию.
                          TClass fun(const TClass& o)
                          {
                            return f(o);//Тут что-нить посложнее, но не важно. При вызове этой функции просто создается измененная копия объекта o.
                          };
                          
                          TClass& fun(const TClass&& o)
                          {
                            return f(o);//Тут что-нить посложнее, но не важно. При вызове этой функции просто возвращается ссылка на старый, но измененный объект o. Эта перегрузка первой функции, но она вызывается только для объектов, что создались на стеке и их можно гарантированно портить.
                          };
                          
                          TClass a = fun(o);//вызывается первая функция
                          TClass a = fun(fun(o));//вызывается первая функция, а потом вторая.
                          fun(TClass(...));//Вызывается вторая функция.

                          Это очень полезная возможность, особенно для оптимизации работы с математикой (например, матрицы или вектора). Все же все перегруженные операторы в С++ - это те же функции, а значит в случае:
                          TClass a=v2+M1*v1+v21*M2;
                          Создаваться на стеке временные объекты будут "много раз за строку", которые можно ради оптимизации безболезненно испортить. Поэтому часто пишут перегрузку операций под оба варианта объектов (для нормальных и временных (правильное название lvalue и rvalue по стандарту)).
                          Ответить
            • Ну вот в новом стандарте C++ можно будет объявить переменную потока. Но делать это по-умолчанию нельзя — дороже обращение, а это противоречит принципу нулевого оверхеда.
              Ответить
              • >дороже обращение
                Это почему это? Дороже создание потока, может быть, но не на много.
                Ответить
                • Потому, что к глобальной переменной обращение идёт по фиксированному адресу, а для переменных потока самое быстрое — это смещение относительно некоторого переменного адреса.

                  Тут ещё забавнее проблема будет. Допустим, в одной части программы мы используем потоки для каких-то сложных вычислений, требующих много переменных потока. В другой части — используем кучу короткоживущих нитей. Эти части могут быть писаны разными людьми, даже быть внутри разных библиотек (детали реализации). И вот окажется, что при создании любого потока нужно будет выделить и проинициализировать ещё тысячи переменных потока, используемых где-то там (а нам не нужных). И вызвать деструкторы при завершении потока.
                  Ответить
                  • >И вот окажется, что при создании любого потока нужно будет выделить и проинициализировать ещё тысячи переменных потока, используемых где-то там (а нам не нужных).

                    Ну зачем же? Ненужные накладные расходы. Инициализируем только те переменные, что используются в потоке, а остальные не инициализируем, раз не нужны. В языке D так и сделано.
                    Ответить
                    • Тогда уровень косвенности при доступе может ещё возрасти. Для D и прочих это не критично, там всё равно сборка мусора.
                      Ответить
                      • >Для D всё равно сборка мусора.
                        Помоему, она там опциональна. Вплоть до того, что в одном коде часть конструкций её использует, а часть нет. Вообщем как и в С++\CLI.

                        >Тогда уровень косвенности при доступе может ещё возрасти.
                        А может и нет. Как реализовали.
                        Ответить
              • > Но делать это по-умолчанию нельзя — дороже обращение

                Пиздец. Типичное крестоблядское уёбищное решение.
                У нормальных людей всё делается так: по умолчанию удобство и надёжность, а для скорости надо немного извратиться. А в С++ - так: по умолчанию скорость, а чтобы оно не глючило, надо извращаться. Счастливой отладки, хули.
                Ответить
          • Ты забываешь один момент. Иммутабельность объектов даёт возможность среде делать множество сверх-оптимизаций. Напр. иммутабельные объекты гарантированно ссылаются на объекты, которые были созданы до них. Это сокращает время трассировки сборщиком мусора.
            Ответить
            • Новая формула вброса.
              Сказать "ты не учёл один момент", или "ты ничего не понял", и продолжить чем-то очевидным, с чем оппонент и не думал спорить.
              Ответить
              • Это не вброс. Ты говорил, что иммутабельность можно легко эмулировать в императивных просто конвенцией именования, а иммутабельность-то в принципе в первую очередь придумана для оптимизаций.
                Ответить
                • Ты сказал, что А можно делать через Б, а на самом деле А нужна для В.
                  Понятно.
                  Ответить
      • Какие ещё смотрел языки и какие понравились?
        Ответить
        • Ещё смотрел ОКАМЛ (о боже, операции для вещественных и для целых пишутся разными символами, о боже, целый тип 31 бит).
          Ответить
      • показать все, что скрытоПредупреждать же надо, блджад! Так звонко КУКАРЕКНУЛ, что до сих пор в ушах звенит...
        Ответить
      • в том-то и дело, что по идее было бы хорошо писать сложные мат. алгоритмы на хаскеле как на сервисе, а потом вызывать их из любого языка, какого хошь - си или дельфи. разумеется писать gui-форму на хаскеле -- извращение.
        Ответить
        • В том-то и дело, что сложные мат. алгоритмы на Хаскелле либо тормозят, либо выглядят как говно.
          Ответить
      • Тут я во многом солидарен с Тарасом. Писать красивый практический код на Haskell можно (Real World Haskell тому подтверждение), но этому надо долго учиться.
        Ответить
    • Лол, какой-то красноглазик проминусовал все посты LinuxGovno
      Ответить
    • Нашёл тоже пример чтобы судить о производительности и идеологии языка. Ты SICP открой, там тоже такой код есть, в разделе про древовидно-рекурсивные процессы. И что теперь, книга - говно и учит маразму? На haskell можно писать очень быстрые программы минимальным числом строк. Вот, к примеру, бесконечный список чисел фибоначчи, требующий для вычисления линейного времени (корекурсия крута):
      fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
      Очень легко реализовать на Haskell красивый алгоритм, вычисляющий заданное число фибоначчи за линейное время.
      Ответить
      • Вы так говорите, будто этого в других языках сделать нельзя.
        Ответить
        • В изначальном варианте коммента была приписка "как и в любом другом языке", но я её убрал, этот факт показался мне очевидным :)
          Ответить
          • То есть вы хотите подчеркнуть, что Haskell не так убог, как мы думаем?
            Откуда вы знаете, как мы думаем?
            Ответить
            • мы знаем, что вы мало думаете :р
              Ответить
            • > вы хотите подчеркнуть, что Haskell не так убог, как мы думаем
              нет, просто код в топике ни о чём. Обычная демонстрация конструкций языка, это ничего не говорит ни о качестве мануала, ни, тем более, языка.
              Ответить

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