Вот ещё задачка.

Есть какой-то список [1,1,2,3,4,5,5,2,3,5,6,7] Надо из этого списка вывести все элементы которые повторяются больше N раз в том же порядке, в котором они впервые появились в начальном списке.

Решение на Go

Как это решается на go? Очень просто:

func CountElement(n int, list []string) []string {  
 var uniqList []string  
 resMap := map[string]int{}  
 for _, el := range list {  
   ex, ok := resMap[el]  
   if !ok {  
     uniqList = append(uniqList, el)  
     resMap[el] = 1  
   } else {  
     resMap[el] = ex + 1  
   } 
 }  
 
 var resList []string  
 for _, el := range uniqList {  
   val := resMap[el]  
   if val >= n {  
     resList = append(resList, el)  
   }
 } 
 return resList  
}

Мы сначала проходим по списку и наполняем resMap для того чтобы считать количество вхождений и uniqList для того чтобы знать порядок в котором элементы впервые появились в списке (ведь если мы просто наполним мапу, то потеряем порядок)

Кстати, наполнять мапу тоже удобно для того чтобы понимать когда элемент впервые появился в списке.

После этого мы проходим по uniqList и проверяем как часто элемент появлялся в начальном списке (дергая мапу)

Если появлялся n или больше раз, то мы можем добавить его в resList который в итоге и возвращаем обратно.

Но на go не интересно.

Haskell 1

Давайте на хаскеле.

Если задачка на go супер просто решается, то на хаскеле она должна решаться ещё проще. Поидее.

А вот и фигушки.

В обычных языках нам доступны последовательные шаги и обращение к состоянию (например к переменным), то в хаскеле нет ни первого, ни второго. Например, в го мы могли обьявить переменную перед циклом и потом её наполнять.

В хаскеле так нельзя, потому что данные имутабельны и всё является функцией.

— Как же они тут живут? - спросите вы.

Ну в основном на различного рода свертках и комбинаторике.

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

Есть две главные функции foldl (идет по списку слева направо) и foldr (наоборот)

Например, мы можем написать что-то вроде

foldl (+) 0 [1,2,3,4]

Функция будет идти по списку слева направо и применять функцию (+) к стеку (который сначала 0), а потом к первому элементу, после чего вызовет себя же

foldl (+) 1 [2,3,4] 
  ↓↓↓
foldl (+) 3 [3,4]
  ↓↓↓
foldl (+) 6 [4]
  ↓↓↓
foldl (+) 10 []

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

Если мы разобьем нашу задачу на части, то увидим что сначала мы формируем список уникальных значений и мапу с количеством повторений, а потом проходим по списку и проверяем условие "больше N повторений"

То есть первую задачу мы однозначно можем выразить через foldl

А стеком для foldl одновременно должны быть и мапа и список повторений

foldl aggregateMap (empty , []) xs

-- xs это имя переменной списка
-- aggregateMap это название нашей будущей функции

Я для этого обьявил синоним для пары

type MapList = (Map String Int, [String]) 

и начал определять функцию

aggregateMap :: MapList -> String -> MapList  
aggregateMap (agMap,list) x  
    | isNothing $ lookup x agMap  = (insert x 1 agMap, x:list)  
    | otherwise = (update (\y -> Just (y+1)) x agMap, list)  

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

Дальше, в теле мы производим паттерн матчинг agMap в мапу, list в список и x в значение которое нам передали

После чего мы выполняем проверку

Если результат поиска в мапе возвращает нам Nothing, то мы добавляем элемент в мапу и список

В всех остальных случаях (то есть когда элемент есть) мы обновляем значение в мапе (прибавляем единицу) и ничего в список не добавляем.

Теперь можно посмотреть как эта функция работает:

>>> aggregateMap (empty , []) "1"
(fromList [("1",1)],["1"])

-- А теперь передадим результат и попробуем добавить 1 или 5, то есть вручную сымитировать foldl


>>> aggregateMap (fromList [("1",1)],["1"]) "1"
(fromList [("1",2)],["1"])

>>> aggregateMap (fromList [("1",2)],["1"]) "5"
(fromList [("1",2),("5",1)],["5","1"])

Соответственно если мы уже попробуем foldl с этой функцией, то всё должно работать

>>> foldl aggregateMap (empty , []) ["1", "1", "2", "3", "2" , "2", "5" ]
(fromList [("1",2),("2",3),("3",1),("5",1)],["5","3","2","1"])

Упс. В списке значения в обратном порядке. Это потому что в aggregateMap мы добавляли элемент в список вот так x:list - то есть каждый последующий элемент добавлялся в начало списка.

А foldl шел слева направо. То есть каждый следующий уникальный элемент становился первым. Впрочем, это не важно сейчас, мы дальше его где-то развернем.

Теперь когда у нас есть мапа и список, нам надо по нему пройтись и сформировать новый список.

Для этого в хаскеле есть функция filter

showList' n (agMap,list) = filter (\x -> fromJust(lookup x agMap) >= n) list

Эта функция первым аргументом принимает фукнцию фильтрования (которая должна вернуть Bool), а вторым — список.

В функции фильтрования (я написал её в лямбда формате, потому что она маленькая) мы принимаем элемент из списка и ищем его в в мапе, после чего сравниваем результат с n

Соответственно всё что нам остается это обьеденить функции

showAggrList :: Int -> [String] -> [String]  
showAggrList n xs = reverse . showList' n  
                              $ foldl aggregateMap (empty , []) xs 

Тут . используется для того чтобы сделать композицию функций для reverse . showList' n — это очень мощная механика хаскеля, которая позволяет составлять из двух функций одну

А $ используется чтобы не ставить скобки (что значительно повышает читаемость)

А зачем мы используем reverse? а затем что нам надо развернуть список обратно.

Итоговый код выглядит вот так.

showAggrList :: Int -> [String] -> [String]  
showAggrList n xs = reverse . showList' n  
                              $ foldl aggregateMap (empty , []) xs  
  
type MapList = (Map String Int, [String]) 
  
aggregateMap :: MapList -> String -> MapList  
aggregateMap (agMap,list) x  
    | isNothing $ lookup x agMap  = (insert x 1 agMap, x:list)  
    | otherwise = (update (\y -> Just (y+1)) x agMap, list)  
  
showList' :: Int -> MapList -> [String]  
showList' n (agMap,list) = filter (\x -> fromJust(lookup x agMap) >= n) list 

Тааак, посмотрим. Ну... как-то это выглядит громоздко.

Haskell 2 (монады)

Я покумекал и переписал вот так:

alternativeL :: Ord a1 => Int -> [a1] -> [a1]  
alternativeL n = liftA2 (>>=) nub $ (\y x -> (y ! x >= n) ?<> [x] )   
. fromListWith (+) . flip zip [1,1..]

Получилось намного компактнее, но и намного непонятнее.

Что происходит?

Для начала надо разобраться что такое >>=

Вкратце - это функция. Она принимает монадическое значение первым элементом, разворачивает его и применяет к результату функцию, которая должна вернуть монадическое значение обратно.

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

Например:

>>> Just 3 >>= (\x -> Just (x+1))
Just 4

А для списка >>= выполняет роль итератора

>>> [1,2,3] >>= (\x -> [x+1])
[2,3,4]

Правда стоит обратить внимание, что возвращать надо не x, но монадический тип (список). Сначала это кажется неудобным, но на деле это как раз расширяет возможности.

-- Вместо одного элемента можно вернуть несколько (например три)
>>> [1,2,3] >>= (\x -> [x,x,x])
[1,1,1,2,2,2,3,3,3]

-- И зачем нужен фильтр, если есть монады? Проверяем условие и возвращаем пустой список, если оно False
>>> [1,2,3] >>= (\x -> x > 2 ? [x] ?? [])
[3]

То есть, если бы у нас уже был список уникальных значений и какая-то мапа, то всё можно было бы переписать как

-- uniqList - список уникальных значений
-- uniqMap  - мапа с количеством повторений
-- filterFromMap - функция для фльтров

uniqList >>= filterFromMap uniqMap

Как же нам получить список уникальных вхождений? Для этого есть функция nub - она принимает на вход список и возвращает уникальные вхождения.

А мапу мы можем очень просто создать вот так

fromListWith (+) . flip zip [1,1..]

[1,1..] создает бесконечный список из единиц, zip - делает из двух списков список пар, а flip - разворачивает аргументы для списка

>>> zip ["a", "b", "c"] [1,2..]
[("a",1),("b",2),("c",3)]
>>> flip zip ["a", "b", "c"] [1,2..]
[(1,"a"),(2,"b"),(3,"c")]

fromListWith создает мапу из списка и применяет функцию, если включи совпали (в нашем случае это + )

а зачем нам тут flip?

да просто чтобы не прописывать xs (ведь именно из xs мы берем ключи)

createMap xs = fromListWith (+) . zip xs [1,1..]

-- это эквивалентно

createMap = fromListWith (+) . flip zip [1,1..]

-- потому что аргумент примениться автоматически

Давайте снова взглянем на нашу монаду

            уникальный массив
     ↓↓↓ 
alternativeL n xs = nub xs >>= filterFromMap n ((fromListWith (+) . flip zip [1,1..]) xs)

Осталось развернуть filterFromMap в отдельную функцию

(\y x -> (y ! x >= n) ?<> [x] )

тут y это мапа, а x - элемент который приходит из монады на сравнение

К тому же, если мы уверены в алгоритме, мы можем вызывать элементы из мапы без обертки Just — через функцию (!)

>>> fromList [("1",2),("2",3),("3",1),("5",1)] ! "1"
2
>>> fromList [("1",2),("2",3),("3",1),("5",1)] ! "2"
3
>>> fromList [("1",2),("2",3),("3",1),("5",1)] ! "9"
*** Exception: Map.!: given key is not an element in the map
CallStack (from HasCallStack):
  error, called at libraries/containers/containers/src/Data/Map/Internal.hs:633:17 in containers-0.6.5.1:Data.Map.Internal

Вторая интересная часть нашего фильтра - функция ?<>

Замечательное свойство монад в том что определение монады подразумевает определение пустого ответа (функция mempty) и преобразования типа к ответу (функция return)

То есть если писать длиное определение то можно написать что-то типа

>>> [1,2,3,4] >>= (\x -> if x > 2 then [x] else [])
[3,4]

>>> [1,2,3,4] >>= (\x -> if x > 2 then return x else mempty)
[3,4]

>>> [1,2,3,4] >>= (\x -> x > 2 ? [x] ?? mempty)
[3,4]

>>> [1,2,3,4] >>= (\x -> (x > 2) ?<> [x])
[3,4]

Таким образом наша финальная функция стала вот такой

alternativeL n xs = nub xs >>= (\y x -> (y ! x >= n) ?<> [x] )   
. ((fromListWith (+) . flip zip [1,1..]) xs)

но мне не нравится что в обоих половинках монады у нас одно и то же xs

Как его убрать? Есть функция liftA2 f1 f2 f3 arg

она применяет arg к f2, arg к f3, а к результатам применяет функцию f1

Таким образом у нас и получилось сократить xs

alternativeL :: Ord a1 => Int -> [a1] -> [a1]  
alternativeL n = liftA2 (>>=) nub $ (\y x -> (y ! x >= n) ?<> [x] )   
. fromListWith (+) . flip zip [1,1..]

-- а $ тут используется чтобы не писать лишние скобки

Впрочем, если вы не хотите пугать людей таким кодом (и не участвуете в соревновании на самой короткий код), то монады можно переписать по-человечески через (do)

alternativeZ :: Ord b => Int -> [b] -> [b]  
alternativeZ n xs = do  
 let uniqMap = fromListWith (+) $ zip xs [1,1..]  
 uniqEl <- nub xs  
 guard (uniqMap ! uniqEl >= n)  
 return uniqEl

В принципе тут происходит тоже самое.

Мы определяем uniqMap так как мы делали это выше а потом для каждого элемента xs делаем проверку (guard) - которая как раз и возвращает пустое значение если проверка не проходится Если всё прошло хорошо и проверка пройдена — возвращаем ключ.

do это просто синтаксический сахар над монадами, так что код и там, и там — вполне равнозначный.

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

Пост получился длинным, но надеюсь вам было интересно.