LINUX.ORG.RU

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

 ,


1

2
  def foo(thisSet: BitSet, thatSet: BitSet): BitSet = {
    var ts = thisSet
    while (!ts.isEmpty && ts.max >= thatSet.max) {
      ts = ts ^ thatSet.map(_ - thatSet.max + ts.max)
    }
    ts
  }

Я имею в виду не рекурсию (ну, с хвостовой оптимизацией можно, на крайняк), а flod/map/etc.

Если что - это я так в полиномиальном базисе собираюсь производить редукцию многочлена. Если есть менее костыльные способы, прошу их в студию. Про ОНБ знаю, это не считается.

★★★★

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

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

vertexua ★★★☆☆ ()
Ответ на: комментарий от cdshines

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

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

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

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

vertexua ★★★☆☆ ()
Ответ на: комментарий от vertexua

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

cdshines ★★★★ ()
Ответ на: комментарий от vertexua

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

cdshines ★★★★ ()

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

cdshines ★★★★ ()
Последнее исправление: cdshines (всего исправлений: 1)
Ответ на: комментарий от anonymous

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

def *(that: Polynomial): Polynomial = Polynomial {
    coeffs.foldLeft(BitSet.empty) { case (acc, i) => acc ^ that.coeffs.map(i +) }
}
А здесь такое разочарование.

cdshines ★★★★ ()
Последнее исправление: cdshines (всего исправлений: 2)
Ответ на: комментарий от cdshines

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

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

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

anonymous ()
Ответ на: комментарий от vertexua

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

apsk ()

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

anonymous ()
Ответ на: комментарий от anonymous

Я же написал - многочлены в полиномиальном базизе над 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 - длина представления модуля (в битах).

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

Взаимно :)

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

cdshines ★★★★ ()
Ответ на: комментарий от cdshines

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

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.