Вот ещё задачка.
Есть какой-то список [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 это просто синтаксический сахар над монадами, так что код и там, и там — вполне равнозначный.
кстати, можно убрать второй проход по списку, если в мапу с повторениями сразу складывать и индекс первого вхождения. Но учитывая что количество уникальных элементов достаточно мало, я решил что лишнее прохождение не повредит производительности, но улучшит читаемость кода
Пост получился длинным, но надеюсь вам было интересно.