Доброго времени суток.
Взялся ради эксперимента сделать OcTree на haskell.
Но пока что не трехмерный случай а одномерный.
Идея в том, что если имеется список точек с координатами от 0 до 1, то мы его делим на две части, в первой части точки с координатой меньше 0.5, во второй — больше 0.5. Далее процесс повторяется, делим точки первой части еще на две (в одной координаты меньше 0.25 в другой больше 0.25), и вторую часть тоже делим на две (до 0.75 и после 0.75). И так впринципе "до бесконечности".

На Хаскеле удобно это сделать так как ленивые вычисления.

По дизайну естественно хочется разделить процесс генерации бесконечного дерева от процесса ограничения этого дерева. Ограничения могут быть разные: по глубине дерева, по количеству точек в интервале, по каким-то характеристикам этих точек, и так далее.

Но вот возникла проблема. При разделении списка С1 текущего уровня на два новых списка хочется чтобы С1 уже память не забирал.
Тоесть смотрю я что в списке С1 1000 точек и думаю, нет, нужно следующий уровень взять, опускаюсь ниже по дереву, и С1 отпускаю чтоб удалился. Так вот не удаляется. Не могу разобраться почему.

Задачу упростил до того что просто на этапе самой генерации дерева обрубаю пустые ветки.
Если без обрубания — память идет только на последний уровень дерева а промежуточные списки действительно удаляются походу.
Если ставлю проверку на пустой список — хранится все списки на всех уровнях.
( см строку с (*) в коде )
Почему так?

Помогите кто может

type Point a = a
type PointList a = [Point a]
data OcTree a = Node (PointList a,PointList a) [OcTree a] | Empty

leafs Empty = [[]]
leafs (Node (items1,items2) forest) = items1 : items2 : concat (map leafs forest)

main = do
    putStrLn $ "Begin"
    seed <- newStdGen
    let randomPoints = randomlist 1000000 seed `use` forceList
    let tree = chopByLevelNumber 15 . makeOcTree $ randomPoints
    let lastlevel = leafs $ tree
    let lastlevelCount = map length lastlevel
    putStrLn $ "  Last level len : " ++ show ( length lastlevel )
    putStrLn $ "  Last level lengths : " ++ show lastlevelCount    
    putStrLn $ "End"

randomlist :: Int -> StdGen -> [Double]
randomlist n = take n . randoms

--
-- utilites
--

forceList :: [a] -> ()
forceList [] = ()
forceList ((!a):as) = forceList as

use :: a -> (a -> ()) -> a
use expr strat = strat expr `seq` expr

--
-- procedures to create an OcTree
--
split2 param items = split2base items
  where split2base [] = ([],[])
        split2base (x:xs) | x < param = (x:s1,s2)
                          | otherwise = (s1,x:s2)
          where (s1,s2) = split2base xs 

makeOcTree :: RealFloat a => PointList a -> OcTree a
makeOcTree items = mkOcTree0 0.5 items
  where 
        mkOcTree0 :: RealFloat a => a -> PointList a -> OcTree a
        --(*) mkOcTree0 _ [] = Empty
        mkOcTree0 param items =  Node (items1,items2) [lt,rt] 
          where 
                (items1,items2) = split2 param items
                lt = mkOcTree0 (0.5*param) items1
                rt = mkOcTree0 (1.5*param) items2
                

--
-- procedures to chop OcTree
--

chopByLevelNumber :: Int -> OcTree a -> OcTree a
chopByLevelNumber _ Empty = Empty
chopByLevelNumber 0 (Node lst _) = Node lst [Empty,Empty]
chopByLevelNumber n (Node lst forest) = Node lst (map (chopByLevelNumber (n-1)) forest)