2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 20:36 


28/07/13
135
Рассмотрим код
Код:
[ (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 и т.п.? Я новичок, не пинайте сильно, пожалуйста.

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 21:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 21:57 


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

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

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 22:24 
Заслуженный участник
Аватара пользователя


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

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

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

user14284 в сообщении #1170425 писал(а):
Да и не только в памяти дело -- чисто эстетически наличие множества имен для посути одной переменной (но изменяемой) выглядит уродски.
А это и не переменная, это всё имена для значений.

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 22:40 
Заслуженный участник
Аватара пользователя


02/08/11
3919
user14284 в сообщении #1170385 писал(а):
Какой всё-таки правильный путь работы с изменяемыми данными в do-блоках, list-comprehensions и т.п.?
В каждом конкретном случае лучший способ свой. В приведённом коде, например, достаточно дать переменным вменяемые имена. Но лучше переписать его так, чтобы не было копипаста — тогда проблема исчезнет сама.
user14284 в сообщении #1170385 писал(а):
Если xs очень большой, то хочется, чтобы "старые" версии съедались сбощиком мусора как можно скорей.
Что в какой момент можно будет собрать определяется алгоритмом. Если бы Haskell разрешал использовать для новой переменной имя, уже занятое старой, это никак не повляло бы на алгоритм и на время жизни объектов.

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 22:55 


28/07/13
135
warlock66613 в сообщении #1170441 писал(а):
Но лучше переписать его так, чтобы не было копипаста — тогда проблема исчезнет сама.

Как например?
warlock66613 в сообщении #1170441 писал(а):
Что в какой момент можно будет собрать определяется алгоритмом. Если бы Haskell разрешал использовать для новой переменной имя, уже занятое старой, это никак не повляло бы на алгоритм и на время жизни объектов.

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

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение20.11.2016, 23:41 
Заслуженный участник
Аватара пользователя


06/10/08
5393
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

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение21.11.2016, 00:01 


28/07/13
135
Xaositect
Спасибо огромное!

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение21.11.2016, 01:36 
Заслуженный участник
Аватара пользователя


02/08/11
3919
Мой вариант:
Используется синтаксис 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]

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение21.11.2016, 04:36 


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

Используется синтаксис 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?

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение21.11.2016, 23:42 


28/07/13
135
Исходный пример допускает много обходных путей. Попробуем усложнить задачу. Пусть дан список списков $[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$. Как бы нормальные люди написали требуемый код?

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение22.11.2016, 00:19 
Заслуженный участник
Аватара пользователя


02/08/11
3919
user14284 в сообщении #1170712 писал(а):
Вот я в силу императивности головного мозга не могу придумать ничего умнее такого
В императивном программировании есть штука под названием цикл. В случае Haskell надо просто записать цикл через рекурсию — это простейший способ, и зачастую даже самый простой (можно сравнить мой код выше, который (целенаправленно) написан без использовнаия рекурсии с кодом Xaositect и _Ivana).

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение22.11.2016, 01:24 


05/09/12
2265
Если не ошибся, то вот мой паракот:
Используется синтаксис 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)
 

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение22.11.2016, 10:12 
Заслуженный участник
Аватара пользователя


06/10/08
5393
Используется синтаксис 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 ]

 Профиль  
                  
 
 Re: Как правильно работать с изменяемыми данными в Haskell
Сообщение22.11.2016, 21:39 


28/07/13
135
Спасибо

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group