Скала: функционально или процедурно

[vak]

Удачный язык Scala: хочешь пиши в функциональном стиле, а хочешь - в традиционном процедурном, на выбор. Сравним два стиля на примере упомянутой задачки Two-Sum.

Функциональный стиль, так называемый "однострочник":

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    nums.zipWithIndex.combinations(2).find(_.map(_(0)).sum == target).get.map(_(1))
}

Процедурный стиль:

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    for (j <- nums.indices) {
        for (i <- 0 until j) {
            if (nums(i) + nums(j) == target) {
                return Array(i, j)
            }
        }
    }
    throw Exception("no solution")
}

Какое из этих двух решений легче понять и доработать при необходимости?

Мне по жизни доводилось решать задачки в функциональном стиле. Делали мы однажды девайс для передачи данных, и надо было научить его тестировать линию связи. Для этого на девайсе нажимается кнопочка, и такой же девайс на удалённом конце линии включает "шлейф" - принятые от нас данные заворачивает обратно к нам. Нужен простой способ послать команду удалённому девайсу, не вмешиваясь в основной поток данных. Имелся медленный однобитовый канал out-of-band. Решение было послать по этому последовательному каналу псевдослучайный поток, сформированный сдвиговым регистром с обратной связью (LSFR).

Математически LSFR выглядит как двоичный полином, к примеру x¹⁶+x¹⁴+x¹³+x¹¹+1. Чтобы выбрать подходящий к ситуации полином, я быстренько сбацал код на Scheme, и через час решение было найдено.

Через пару лет мы разработали другое устройство, для гораздо более скоростных линий связи, но с другим характером помех в линии. Старые полиномы больше не подходили: наблюдались ложные срабатывания. Надо было подобрать другие полиномы, подлиннее. Достал я старый код и... убил пару дней, пытаясь в нём разобраться. Плюнул, переписал на Си, и код стал понятным.

Перефразируя Форреста Гампа, это всё, что я могу сказать о моём отношении к функциональному программированию. 😀

Comments

[spamsink]

Тут ещё и то, что при взгляде на процедурный код сразу видна более точная нижняя грань его вычислительной сложности, чем при взгляде на функциональный код.

[vit_r]

def twoSum(    nums: Array[Int]
             , target: Int
             )
    : Array[Int] = {

    nums
        .zipWithIndex
            .combinations(  2 )
                .find(          _.map(  _( 0 ) 
                                        )
                                        .sum 
                                == target
                                )
                        .get
                            .map( _( 1 ) )

}

[euthanasepam]

> полином


Доколе исконно посконное слово многочлен будет в интернетах ущемляемо, попираемо и сугубо аще ибо?

[vak]

Я вырос при советской власти, для меня многочлен == партсобрание. 😀

[mikerrr]

Так их!))

[juan_gandhi]

В Москве многочлены, в Питере полиномы.

[euthanasepam]

Процедурное человеку наглядней и понятней, поскольку мы рассуждаем и вообще мыслим процедурно, и мир вокруг нас в некотором смысле процедурен и для нашего восприятия последователен (с точки зрения линейности и направленности времени, каким его мы себе обычно представляем). У математиков своя реальность, где, помолясь, иногда можно (и даже нужно) сократить записи, упаковав цепь рассуждений в одну работающую формулу. Простому же человеку готовая формула может и не подсказывать о скрывающихся за нею рассуждениях и операциях, может и вовсе ничего не подсказывать, выглядя как китайская грамота. Если исходить из того, что предназначение программного текста — чтение его прежде всего человеком, то предпочтительней понятность и наглядность.

[vanja_y]

и мир вокруг нас в некотором смысле процедурен и для нашего восприятия последователен

Зависит от тренировки. Если много лет писать однопоточный код, то восприятие будет поледовательным. Если разрабатывать схемы на каком-нибудь VERILOG, то будет вполне себе паралельным.

Для меня вот при написании статей самая большая сложность выстроить доказательства в последовательном, линейном порядке, потому что внутренне я их перживаю как нечто единное/одномоментоное, сосотоящее из сети фактов соединенных импликациями.

[euthanasepam]

Как в анекдоте: «Выходите вы на пляж, а вокруг станки, станки, станки…»

[juan_gandhi]

Мир вокруг вас процедурен исключительно в вашем восприятии.

[vanja_y]

Без list-comprehension життя погане і незручне:

import qualified Data.Vector as V 

twoSum nums target = head [ (i,j) | j <-[0..(V.length nums)-1],
                                    i <- [0..j-1], 
                                    nums ! i + nums ! j == target 
                          ]

Edit: не помітив, що потрібні індекси, а не значення...

[juan_gandhi]

Однострочники и ФП довольно ортогональны. На джаве тоже был одно время принят такой стиль, однострочный. Хрен что отладишь.

Первое я бы написал так:

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val pairs = nums.zipWithIndex.combinations(2)
    val found = pairs.find(_.map(_._1).sum == target)
    found.get.map(_._2) // IRL, don't use `get`!
  }

А второе более скально:

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    for {
      j <- nums.indices
      i <- 0 until j
      if nums(i) + nums(j) == target} {
        return Array(i, j)
      }

    throw new Exception("no solution")
  }

[vak]

Красиво!

[malyj_gorgan]

Ех, треба було намагатися читати ваші пости про Скалу ще давніше.
Зараз попав в команду, де основні процедури роботи з даними написані на Скалі, але не надто задокументовані, а людей, які писали код, часто вже поряд нема. Моя роль -- чи то методологічний начальник, чи то glorified к'юей, словом, треба розібратися, як воно все у них працює. І що виходить: прочитати скальний код, щоби точно сказати, що там у них під кришкою капота, ніхто ніфіга не може. Ну добре, я, який після C і фортрана щось писав уже на матлабах і пітонах, але ж самі девелопери в тому плавають. Був би нормальний SQL, я би розібрався сам, а так виходить, що вони, з одного боку, всі такі горді "у нас все функціонально і масштабується", а, з другого боку, розібратися, як хоч щось в їхньому аналізі покращити, займає стільки часу, що ніякої радості. Вони, в результаті, навіть власні ідеї переписують часом з нуля, замість поправити готову функцію.

Все як з іншими споживчими продуктами: там, де раніше було трохи довше і незґрабніше зроблено, зате працювало довго і ремонтувалося, зараз все дешевше і гарніше, але як тільки що не так, доводиться викидати старе і купувати нове.

[juan_gandhi]

В скале много разных культур. Есть древние. Есть новые (их две, Cats и Zio). И есть разного рода сумасшедшие. Одни лезут со свободными монадами (не зная теории категорий, не знают и, что они не всегда существуют), другие пишут просто код в одну строчку - тест-то писать лень.

Короче, я думаю, можно к скале подходить как к любому нормальному языку: - давай читабельность - давай покрытие тестами - желательно унификацию библиотек, чтобы не было пять разных парсеров джейсона

Преимущество скалы не в том, чтобы писать заумный бред, а в том, что можно писать чистенький код разборчиво и без мусора.

[malyj_gorgan]

В даному випадку я, чесно, не знаю, чи уніфікація бібліотек тут буде в плюс чи в мінус.
Код-то не якийсь перформанс комп'ютейшн, а робота з даними, з кількома конкретними таблицями, кожна з яких досить унікальна. Проблема нечитабельності в тому, що в процесі абстрагування тих чи інших процедур і використання додаткових бібліотек, маскується розуміння того, які саме дані ми сюди притягнули, що групуємо, що фільтруємо, що лишаємо, як є.
Тобто, тут суть не в тому, як вони закодували, а в тому, що для читабельності з точки зору дата сайєнтіста такий код треба було з усіх сторін обзадокументувати ("а інпути у нас бувають такі, а типові аутпути сякі" і т. п.)

[juan_gandhi]

Да это тоже верно.

Насчет же библиотек - вечная тема в скальной среде. Можно ли уже на 13-ю переходить, или таки у нас вот та библиотека не работает с 13-й, а зачем нам та, если есть эта, а есть и эта... Короче, иногда кажется, что проще вообще свой код написать и не мучаться. Видел и свою версию Спарка, в предыдущей конторе, и свою версию Сваггера (в этой конторе) - но со Сваггером, похоже, такая фигня, что мы и мейнтейнеры, только этого никто не помнит.

[malyj_gorgan]

Другий абзац: той випадок, коли мені абсолютно все-одно, якою мовою написано текст. Я однаково розумію рівно 0% вкладеного змісту :(

[vak]

Це я називаю write-only код. Коли один програміст може такий код написати, але потім ніхто вже неспроможний цей код зрозуміти та розвивати. Деякі мови та стилі програмування провокують на write-only код.

[malyj_gorgan]

Повбивавби

(disclaimer: часом, читаючи власний код кількарічної давності, я думаю так само... але я, принаймні, коментую. А вони думають, що пишуть в self-documenting парадигмі, а потім читають власний код:
(Я): "А що це у вас тут?"
(вони): "А це ми тут берем результати такого-то метода з ... дивимося...дивимося... такої-то бібліотеки."
(Я): "А що той метод робить? Які там входи/виходи (типові значення, макс/мін, все таке, data science, не псячий хвіст -- у нас весь код про те, як десь взяти якісь дані, схрестити їх з іншими даними, якось перетворити/пофільтрувати/згрупувати, і повернути назад)?"
(вони): "Ой, не знаємо, це ХХХ написав, він уже тут не працює."
(Я): "Ну то подивіться, хто у нас тут Скалу любить і захищає?"
Вони лізуть в тут бібліотеку, а там такий самий самозадокументований код, і хрін його знає, що там таке...

Зате "scalable solution, would be much uglier in SQL". Щаз!

[juan_gandhi]

Well, talking about SQL, I'm afraid most programmers, object-oriented or functional, just don't get SQL. Can't explain it, but they don't.

[malyj_gorgan]

Я не претендую, що я "get SQL"
Просто, мова, де дуже зручно писати і читати взаємодію з даними, збереженими в relational форматі.
Якщо треба щось з цими даними робити, воно в сіквелі не завжди найзручніше. Але -- "і читати" :)

[iamjaph]

Решил посмотреть как Two-Sum задачу решить, используя Standarm ML.
Оказалось, что в базовой библиотеке нет ни zipWithIndex, ни combinations, ни sum.

Есть только findi: (int * 'a -> bool) -> 'a vector -> (int * 'a) option

Решил сделать findijr, который ищет не с 0, а с j элемента и возвращает то, что вернула функция поиска:

val findijr = fn: (int * 'a -> 'b option) -> 'a vector -> int -> 'b option

Тогда решение Two-Sum:

fun twoSum nums target = findijr (fn (i, vi) => (
     findijr (fn (j, vj) =>
       if vi + vj = target then SOME (Vector.fromList [i, j]) else NONE
     ) nums i
  )) nums 0

Какой это стиль получился?

[juan_gandhi]

ML-ский, я б сказал.

Нормальный. Функциональный.