Как правильно работать с изменяемыми данными в Haskell

[user14284]

Рассмотрим код

[ (a,b,c,d) |
    a <- xs,
    let xs' = filter (/= a) xs,
    b <- xs',
    let xs'' = filter (/= b) xs',
    c <- xs'',
    let xs''' = filter (/= c) xs'',
    d <- xs''' ]

Тут мы постоянно изменяем xs, но вынуждены давать новые имена, что делает код уродским. Если xs очень большой, то хочется, чтобы "старые" версии съедались сбощиком мусора как можно скорей. В данном конкретном примере можно поступить проще (использовать один xs, но на каждом шаге выкидывая всё увеличивающийся список ненужных элементов). Этот пример лишь для иллюстрации общей проблемы.

Какой всё-таки правильный путь работы с изменяемыми данными в do-блоках, list-comprehensions и т.п.? Я новичок, не пинайте сильно, пожалуйста.

[arseniiv]

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

[user14284]

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

Какие разумные способы предлагает Haskell кроме как создания на каждом этапе списка с новым именем (тем самым не давая сборщику мусора стереть из памяти старый список). Да и не только в памяти дело -- чисто эстетически наличие множества имен для посути одной переменной (но изменяемой) выглядит уродски.

[arseniiv]

Ничего настолько общего в мои знания не входит. Могу только сказать про монады State, ST и (если всё плохо) IO, но я не вижу, где бы они помогли здесь, и не разбираюсь во второй из них.

user14284 в сообщении #1170425 писал(а):

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

(Всё равно наверняка в данном случае список — не лучший контейнер.)

user14284 в сообщении #1170425 писал(а):

Какие разумные способы предлагает Haskell кроме как создания на каждом этапе списка с новым именем (тем самым не давая сборщику мусора стереть из памяти старый список).

А что, со старым он обязательно сразу же сотрёт? Вы проверяли? [UPD: А, ну я щас проверил и увидел, что со старым не получится. Видимо, это воспринимается как определение через себя, сразу не понял.] Вообще-то в некоторых случаях GHC выдаёт код, который не создаёт лишних списков (list fusion).

user14284 в сообщении #1170425 писал(а):

Да и не только в памяти дело -- чисто эстетически наличие множества имен для посути одной переменной (но изменяемой) выглядит уродски.

А это и не переменная, это всё имена для значений.

[warlock66613]

user14284 в сообщении #1170385 писал(а):

Какой всё-таки правильный путь работы с изменяемыми данными в do-блоках, list-comprehensions и т.п.?

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

user14284 в сообщении #1170385 писал(а):

Если xs очень большой, то хочется, чтобы "старые" версии съедались сбощиком мусора как можно скорей.

Что в какой момент можно будет собрать определяется алгоритмом. Если бы Haskell разрешал использовать для новой переменной имя, уже занятое старой, это никак не повляло бы на алгоритм и на время жизни объектов.

[user14284]

warlock66613 в сообщении #1170441 писал(а):

Но лучше переписать его так, чтобы не было копипаста — тогда проблема исчезнет сама.

Как например?

warlock66613 в сообщении #1170441 писал(а):

Что в какой момент можно будет собрать определяется алгоритмом. Если бы Haskell разрешал использовать для новой переменной имя, уже занятое старой, это никак не повляло бы на алгоритм и на время жизни объектов.

Я не знаю всех тонкостей, но наивно считаю, что пока имя объекта в области видимости, его сборщик мусора не тронет. И наоборот. Нет?

[Xaositect]

arseniiv в сообщении #1170437 писал(а):

Ничего настолько общего в мои знания не входит. Могу только сказать про монады State, ST и (если всё плохо) IO, но я не вижу, где бы они помогли здесь, и не разбираюсь во второй из них.

Вот как это можно написать с трансформером State. Хотя, конечно, этот конкретный пример понятнее пишется по-простому.

Используется синтаксис Haskell

module Main where

import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

test = [1,1,2,3,4,2,1]

joinT :: (MonadTrans t, Monad m, Monad (t m)) => t m (m a) -> t m a 
joinT = join . fmap lift

getM :: (Monad m) => StateT (m a) m a 
getM = joinT get

transform :: (Eq a) => [a] -> [(a,a,a,a)]
transform xs = 
  flip evalStateT xs $ do
    a <- getM
    modify (filter (/= a))
    b <- getM
    modify (filter (/= b))
    c <- getM
    modify (filter (/= c))
    d <- getM
    return (a,b,c,d)

main = print $ transform test

-- Вс ноя 20, 2016 21:50:48 --

user14284 в сообщении #1170451 писал(а):

Как например?

Используется синтаксис Haskell

distinct :: (Eq a) => Int -> [a] -> [[a]]
distinct 0 _ = [[]]
distinct n xs = [ (h:ts) | ts <- distinct (n - 1) xs , h <- xs, h `notElem` ts]

transform :: (Eq a) => [a] -> [(a,a,a,a)]
transform = map (\[d, c, b, a] -> (a, b, c, d)) . distinct 4

[user14284]

Xaositect
Спасибо огромное!

[warlock66613]

Мой вариант:

Используется синтаксис Haskell

transform :: Eq a => [a] -> [(a, a, a, a)]
transform xs =
  map (quadrupel . fst) $ head $ drop 4 $ iterate enmix [([], xs)]
  where
    quadrupel :: [a] -> (a, a, a, a)
    quadrupel (d : c : b : a : []) = (a, b, c, d)
    quadrupel _ = error "quadrupel"
    enmix :: Eq a => [([a], [a])] -> [([a], [a])]
    enmix = concat . map (enproduct . enfilter)
    enfilter :: Eq a => ([a], [a]) -> ([a], [(a, [a])])
    enfilter (r, xs) = (r, [(x, filter (/= x) xs) | x <- xs])
    enproduct :: ([a], [(a, [a])]) -> [([a], [a])]
    enproduct (r, xs) = [(x : r, t) | (x, t) <- xs]

[_Ivana]

О, такая паралимпиада, как же я могу пропустить! :)

Используется синтаксис Haskell

foo 0 _ = [[]]
foo n l = l >>= \x -> map (x:) . foo (n-1) $ filter (/= x) l

task = map (\[a,b,c,d] -> (a,b,c,d)) . foo 4
 

user14284, мозги мышление надо менять, а не состояние.

user14284 в сообщении #1170425 писал(а):

чисто эстетически наличие множества имен для посути одной переменной (но изменяемой) выглядит уродски

и именно поэтому вы рисовали ваши a, b, c, d?

[user14284]

Исходный пример допускает много обходных путей. Попробуем усложнить задачу. Пусть дан список списков $[X_1,\ldots,X_n]$ типа Ord a => [[a]]. Найдём список всех возрастающих последовательностей $[x_1,\ldots, x_n]$ таких, что разные $x_i, i>1$ взяты в разных списков, но первый элемент $x_1$ взят из $X_1$. Вот я в силу императивности головного мозга не могу придумать ничего умнее такого:

Используется синтаксис Haskell

f :: Ord a => [[a]] -> [[a]]
f ls = 
[ [x1,x2,x3,x4] |
    let xs1 = head ls,
    x1 <- xs1,
    xs2 <- delete xs1 ls
    x2 <- xs2,
    x2 > x1,
    xs3 <- delete xs2 ls,
    x3 <- xs3,
    x3 > x2,
    xs4 <- delete xs3 ls,
    x4 <- xs4,
    x4 > xd ]    
 

который, к тому же, требует фиксированного $n$. Как бы нормальные люди написали требуемый код?

[warlock66613]

user14284 в сообщении #1170712 писал(а):

Вот я в силу императивности головного мозга не могу придумать ничего умнее такого

В императивном программировании есть штука под названием цикл. В случае Haskell надо просто записать цикл через рекурсию — это простейший способ, и зачастую даже самый простой (можно сравнить мой код выше, который (целенаправленно) написан без использовнаия рекурсии с кодом Xaositect и _Ivana).

[_Ivana]

Если не ошибся, то вот мой паракот:

Используется синтаксис Haskell

get 0 _ = [[]]
get n l = li >>= \(x,i) -> map (x:) . get (n-1) $ rest i
    where li = zip l [1..]
          rest i = map fst $ filter ((/= i).snd) li

foo 0 _ = [[]]
foo n (a:as) = a >>= \x -> map (x:) $ foo (n-1) as

sorted l = l == sort l

task n (l:ls) = filter sorted $ l >>= \x -> map (x:) r where
    r = get (n-1) ls >>= foo (n-1)
 

[Xaositect]

Используется синтаксис Haskell

distinct :: (Eq a) => [[a]] -> [[a]]
distinct [] = [[]]
distinct (xs:xss) = [ (p:ps) | p <- xs , ps <- distinct xss, p `notElem` ps ]

task :: (Eq a) => [[a]] -> [[a]]
task xss = [ (p:sort ps) | (p:ps) <- distinct xss, all (p<) ps ] 

[user14284]

Спасибо