из твоего поста, балбес

А подскажи плз, можно для задания:

удалить дублирующиеся подряд символы в строке

сделать красивее код:

    val input = "hhhxxxxxhfgffhh";
    removeDup(input.toList)

  def removeDup[T](array: List[T]): List[T] = {
    removeDuplicate(array.head, array)
  }

  def removeDuplicate[T](head: T, array: List[T]): List[T] = {
    if (array.isEmpty)
      head::array
    else if (head == array.head)
         removeDuplicate(head, array.tail)
    else head::removeDuplicate(array.head, array.tail)
  }

и вообще я не понял длинной строки return…

Идея алгоритма(упрощенная):

Нужно найти сумму квадратов m максимальных чисел в массиве a, которую обозначим f(a, m).

Выбираем какой-то элемент массива a. Для простоты возьмем a[0].

Разделим массив a на две части x и y такие, что:

x[i] > a[0]

y[i] <= a[0]

Пусть length(x) и length(y) - длины массивов, тогда

Если length(x)>m, f(a, m) = f(x, m).

Если length(x)<=m, то f(a, m) = sumSquared(x) + f(y, m-length(x))

В сортировках асимптотика считается по количеству сравнений, валенок.

ты про что вообще гавкаешь-то?

разве не за O(n*log(n))?

За O(n). Тут мы так же, как и в быстрой сортировке, делим массив на две части, но рекурсивный вызов делаем только для одной части массива

На хаскеле так:

f [] = []
f (x:xs) = x: f (dropWhile (==x) xs)

> f "hhhxxxxxhfgffhh"
"hxhfgfh"

Если я правильно понял задание.

Да, понял верно, спасибо) Найти бы для скалы аналог dropWhile

Разделим массив a на две части x и y такие, что: x[i] > a[[0]]

ну пусть все числа неотрицательные. Ну и будет у тебя a[[0]]==0, и всё окажется внутри x. Причём сссно в несортированном виде.

Ты наверное qsort хотел написать, дык там сложность в лучшем случае O(n*log(n)), к примеру, если ты хочешь сортануть (16),

1. делишь (16) t+=16

2. делишь (8) и второй (8) t+=2*8

3. делишь 4шт по (4) t+=4*4

4. делишь 8шт по (2) t+=8*2

итого t = 16*4 = 64 = 16*log₂(16).

Это если тебе везёт, если не очень, то будет дольше.

Я может что лучше придумаю. А может и нет.

А можешь пошагово объяснить что происходит в функции?

Это если тебе везёт, если не очень, то будет дольше.

Я же написал, что это упрощенный вариант. В моем сишном коде я делю массив на три части (меньшая, строго равная и большая) и делю не по первому элементу, а по медиане трех элементов.

Да, у моего алгоритма сложность O(n) в среднем, так же как и у квиксорта сложность O(n log n) в среднем.

Я тут уже кидал ссылку на алгоритм, который находит медиану массива за O(n), http://en.wikipedia.org/wiki/Median_of_medians. Используя этот алгоритм, можно получить сложность O(n) и для худшего случая, но на практике он не нужен. Медиана медиан — главным образом теоретический результат.

$ echo "hhhxxxxxhfgffhh" | sed -r 's/(.)(\1)+/\1/g'
hxhfgfh

man 3 regexec если на сишке или плюсах.

а как у регекспов с работой на больших строках?

Если это еще из интервью, то вот так: http://ideone.com/zuhU4X

Выебнулся со StringContext ради интервью, да)

Я тут уже кидал ссылку на алгоритм

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

и в твоём случае делить надо не по медиане, а по W, которое наибольшее из M-N чисел, которые не больше W.

меньшая, строго равная и большая

строго равная зачем?

а как у регекспов с работой на больших строках?

нормально. http://swtch.com/~rsc/regexp/regexp1.html почитай на всякий.

APL рулит! ;) Жалко, что его так незаслуженно забыли.

Понимаю сразу, насколько я вообще не разбираюсь в скале) Пользуясь случаем, что можно прочитать чтобы понять что такое:

case all @ (`chr` :: rest) => all

неведомая ёжиковая фигня

И ещё на гитхабе был найден такой пример решения:

  def compress[T](values: List[T]) : List[T] = 
    compressTail(Nil, values)
  @tailrec
  def compressTail[T](seen: List[T], remaining: List[T]) : List[T] = 
    remaining match {
      case Nil                      => seen
      case x :: y :: xs if (x == y) => compressTail(seen, y :: xs)
      case x :: xs                  => compressTail(seen ::: List(x), xs)
    }
Вас ис дас x,y и xs? Гугл молчит или я не умею гуглить

Ну ладно, мы тоже так можем!

def dd(seq: String): String =
    seq.headOption.map(hd => hd + dd(seq.tail.dropWhile(hd == _))).getOrElse(seq)

Про pattern matching что-нибудь.

@ нужно для того, чтоб забиндить имя к тому, что матчишь (ко всему или к куску), а `chr` в backticks взято, чтобы сматчить со значением переменной chr, иначе она будет просто новой локальной переменной, содержащей голову списка.

Но мне больше вариант Waterlaz понравился. Правда, из-за того, что строки в скале нельзя матчить как списки - hd :: tl не работает, приходиться извращаться с hd + tl, а это уже как-то неканоничненько)

Вариант на Clojure:

(defn f3 [a b c]
        (->> [a b c]
             (sort)
             (drop 1)
             (map #(* % %))
             (apply +)))

Проверка:
> (f3 2 3 1)
13

Для неопределенного количества чисел и для заданного количества максимальных элементов:

(defn f [n & elements]
        (->> (-> (iterate (fn [[res rem]]
                            ((juxt (partial conj res)
                                   (partial disj rem))
                             (apply max rem)))
                          [() (into #{} elements)])
                 (nth n)
                 (first))
             (map #(* % %))
             (apply +)))

Проверка. Сумма квадратов трех максимальных элементов для шести чисел:
> (f 3 1 2 5 4 3 6)
77

Для последнего (общего) случая имхо императивный алгоритм будет более эффективным, но и более громоздким.

APL рулит! ;) Жалко, что его так незаслуженно забыли.

Ну не так уж и забыли, просто боятся. А так я лично знаю чувака, который практически каждый день IRL его использует для всякой статистики.

удалить дублирующиеся подряд символы в строке

На Clojure:

Неленивый аналог (нужен ленивый, добавить lazy-seq перед cons) хаскельского варианта Waterlaz-а:

(defn f [[x & xs :as col]]
  (when (not (empty? col))
    (cons x (drop-while #(= x %) (f xs)))))

Еще вариант:

(->> "hhhxxxxxhfgffhh"
     (partition 2 1)
     (filter (partial apply not=))
     (map first)
     (apply str))

"hxhfgf"

Функциональненько и на эрлангочке

do([A | [B | Tail]]) ->
  {C, D} = lists:foldl(
    fun
      (H, Z = {X, Y}) when (H < X) and (H < Y) ->
        Z;
      (H, {X, Y}) when (H >= X) and (H < Y) ->
        {H, Y};
      (H, {X, Y}) when (H =< X) and (H > Y) ->
        {X, H};
      (H, {X, Y}) when (H > X) and (H > Y) and (X > Y) ->
        {X, H};
      (H, {X, Y}) when (H > X) and (H > Y) and (X < Y) ->
        {H, Y}
    end,
    {A, B},
    Tail),
    C * C + D * D.

Еще раз - твой код на хаскеле не работает.

common lisp :)

(defun sum-sqr-of-2-max (xs) 
  (let ((mm (reduce 
      (lambda (a x) (cond ((> x (car a)) (cons x (car a))) ((> x (cdr a)) (cons (car a) x)) (t a))) 
      (cddr xs) 
      :initial-value (cons (car xs) (cadr xs))))) 
    (+ (expt (car mm) 2) (expt (cdr mm) 2))))

(sum-sqr-of-2-max '(1 2 3 2 3))

18

Еще раз - твой код на хаскеле не работает.

Подробнее можешь? Выдает неправильный ответ? На каких данных?

Ну так тут получается

1. делишь (16) t+=16

2. делишь только один (8) t+=8

3. делишь только один (4) t+=4

4. делишь один (2) t+=2

Итого 2n

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

Да.

и в твоём случае делить надо не по медиане, а по W, которое наибольшее из M-N чисел, которые не больше W.

Нет. Вообще говоря, медиана медиан позволяет найти m-е по старшенству число в массиве. Достаточно один раз найти такое число x, а дальше посчитать сумму квадратов всех чисел, которые меньше x и добавить некоторое количество x^2, если в массиве было несколько одинаковых x.

строго равная зачем?

Улучшает работу алгоритма на массивах, где много одинаковых элементов.

Могу

f [] = []
f (x:xs) = x: f (dropWhile (==x) xs)

(==x) — функция, которая дает результат True только для x.

(==4) 4  — True

(==4) 3  — False

(==4) 2  — False

dropWhile (==x) xs  — последовательно удаляет элементы из списка, пока они равны x.

dropWhile (=='b') «bbbxyz»  — результат «xyz»

f (x:xs) = x: f (dropWhile (==x) xs) — для списка, у которого в голове стоит x, а дальше идет хвост xs, из xs удалить все x, что стоят вначале и к результату применить f.

Нет. Вообще говоря, медиана медиан позволяет найти m-е по старшенству число в массиве. Достаточно один раз найти такое число x, а дальше посчитать сумму квадратов всех чисел, которые меньше x и добавить некоторое количество x^2, если в массиве было несколько одинаковых x.

ну пиши, раз взялся. Ещё раз: я решил задачу ТС, и её обобщил. Однако я не обещал, что обобщение будет работать во ВСЕХ случаях хорошо. Лично мне виделось естественным, что число минимумов небольшое и константное. Ну и обобщение мне нужно было лишь для того, что-бы наметить решение в функциональном стиле.

Улучшает работу алгоритма на массивах, где много одинаковых элементов.

преждевременная оптимизация == зло.

Сложно, так вот чуть менее красиво, но зато читается легче:

def f(s:String):String = 
    if (s.isEmpty) s else s.head + f(s.tail.dropWhile(_ == s.head))

Да любое бы рабочее принял, какая разница-то?

Да, я потом тоже к такому пришел.

не знаю, было ли такое:

return a^2+b^2+c^2 - min(a,b,c)^2