Как канонічно-функционально это пишется?

Как канонічно-функционально это пишется?

Определяешь моноид поиска максимума, а потом просто sum или смотря как называется функция

Какая сумма? ЯННП, можешь поподробнее?

Моноид - определение транзитивной операции «умножения» над элементами множества и «еденицы» множества. Они абстрактны.

Конкатенция строк и «» - моноид. 1 и умножение - моноид. 0 и сумма - моноид.

Это так, для просвещения.

Вот я посмотрел второй раз, вроде его сюда не так просто приткнуть. Да и самого начала я пошутил, но разработчики библиотеки scalaz не шутят, там реально есть класс моноид и они думают что все будут ним пользоваться.

Я знаю, что такое моноид) Я тоже не понял, к чему это здесь.

И да, моноид - это не «0 и сумма», а, например, «целые числа образуют моноид по сложению относительно 0». Для просвещения :/

Никак. Либо хвостовая рекурсия, либо комбинатор заменяющий этот конкретный кейз.

Печально :( Нагородил костыль поверх foldLeft, но оно как-то так стремно выглядит, что я отказался от этой затеи. Тогда такой вопрос - т.к. эта функция не меняет состояния окружения и не выставляет кишки напоказ, может ли она при всей мутабельности считаться чистой?

И, если можешь, покажи комбинатор, потому что я не осилю. Хотя бы из спортивного интереса.

Ох, мне прямо обидно! Я так аккуратно написал умножение:

def *(that: Polynomial): Polynomial = Polynomial {
    coeffs.foldLeft(BitSet.empty) { case (acc, i) => acc ^ that.coeffs.map(i +) }
}

покажи комбинатор

Ну просто подставить произвольные функции куда надо:

  def foo(pred: BitSet => Boolean, f: BitSet => Bitset): BitSet => BitSet = { thisSet =>
    var ts = thisSet
    while (pred(ts)) {
      ts = f(ts)
    }
    ts
  }

Хм, что-то сигнатура мне очень напоминает. Где-то в исходниках hof скалы я что-то такое видел, по-моему. Нужно поискать.

Так еще можно:

  def appWhile(...): ... = {
      def helper(...): ... = 
          if (pred(ts)) helper(f(ts))
          else ts
      helper
  }

Ассоциативной, а не транзитивной. Последнее свойство для бинарных операций (не путать с бинарными отношениями) вообще не определено.

И что эта хренотень делает? Хоть бы пример привел.

Я вчера был не в себе. Простите мой бред

Я же написал - многочлены в полиномиальном базизе над GF(2) делит.

БитСет представляет набор коэффициентов (0 или 1), т.е., к примеру, BitSet(0,1,2) ~ x^2 + x + 1, a BitSet(1) ~ x. Таким образом, если делать редукцию по модулю, например, x^2 + x + 1, многочлена x^4 + x^3 + x, получим (в представлении коэффициентов это (11010 mod 111)): 11010 mod 111 -> 110 mod 111 -> 1 => это просто единица. И в самом деле, если разделить руками на листочке, так и будет. То есть просто слева направо складываются (вообще - отнимаются, но мы же в GF(2)) группы по n чисел, где n - длина представления модуля (в битах).

Я же написал
многочлены в полиномиальном базизе над GF(2) делит.

Сорри, тут не все PhD в абстрактной математике.

Попытался изобразить твое словесное описание: https://gist.github.com/anonymous/7335362

тут не все PhD
import Control.Applicative ((<$))

Взаимно :)

Но, кажется, я понял, и, если понял правильно, то это хвостовая рекурсия. Я так полагаю, простой сверткой все-таки не обойтись, ну да и ладно.

если понял правильно, то это хвостовая рекурсия

Почти, это корекурсия (нехвостовая). Технически, правда, хаскель разницы между рекурсией/корекурсией не делает. Простой foldr и сложный unfoldr дуальны.