2votos

La tela de araña en Haskell

por josejuan hace 6 años

Inmutable con listas adjacentes, recrear para cada araña (función "a") itera un promedio de "size" en la estructura (es decir, la raíz del número de nodos).

Un problema fácil de resolver imperativamente... ¿y funcionalmente? (inmutabilidad y transparencia referencial). Aun así (el enfoque funcional), creo que puede ser un buen kata para practicar punteros y/o TAD's.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
-- dado un problema, devuelve infinitos pasos de ejecución 
getSteps :: Int -> [(Int, Int)] -> [[Int]] -> [Int] -> [([(Int, Int)], [[Int]])] 
getSteps size s g r = (s, g) : getSteps size s' g' r' 
  where s' = [v (s!!n) (m!!n) | n <- [0..size - 1]]  -- new spiders positions 
        g' = foldl a g s'                            -- new grid counter 
        (m, r') = splitAt size r                     -- using infinite randoms 
 
        -- recreate grid traversing coords 
        a (z:zs) (x, 1) = a' z x : zs 
        a (z:zs) (x, y) = z : a zs (x, y - 1) 
        a' (w:ws) 1 = (w + 1) : ws 
        a' (w:ws) x = w : a' ws (x - 1) 
 
        -- move speeder to new position 
        v (x, y) r = if r `mod` 2 == 0 then (m x, y) else (x, m y) 
          where m z = q (z + if (r `div` 2) `mod` 2 == 0 then -1 else 1) 
                q z = if z <= 0 then 2 else if z > size then size -1 else z 
 
 
 
 
 
 
 
 
 
 
-- usage ========================================= 
import System.Random 
 
-- aquí "getSteps" 
 
getRandoms :: (RandomGen g, Random a) => g -> [a] 
getRandoms g = r: getRandoms h 
  where (r, h) = random g 
 
getSpiders :: Int -> [(Int, Int)] 
getSpiders 0 = [] 
getSpiders n = (n, n): getSpiders (n - 1) 
 
getGrid :: Int -> Int -> [[Int]] 
getGrid _ 0 = [] 
getGrid size n = getGrid size (n - 1) ++ [t (n - 1) ++ [1] ++ t (size - n)] where t z = take z $ repeat 0 
 
 
main = do 
  let size = 50 
  rndList <- getStdGen 
  let randomList = getRandoms rndList 
  print $ show $ head $ drop 100 $ getSteps size (getSpiders size) (getGrid size size) randomList 
4 comentarios
0votos

Escrito por jneira hace 6 años

Compacto te ha quedado... ¿podrias extenderte un poco (o apuntar algun link) sobre el calculo del coste [O(m^1/2)|m=nº nodos] de usar una lista de adyacencentes para representar un grafo ?
1votos

Escrito por josejuan hace 6 años

Una lista adjacente suele ser sparse, en nuestro caso no lo es y por tanto es más fácil dejar claro el coste.

Sea "Y" una coordenada, "X" otra coordenada y un "-" o "|" un enlace de listas, entonces tenemos que nuestra estructura podría representarse como:

|
Y - X - X - ... - X - X - []
|
Y - X - X - ... - X - X - []
|
....................
|
Y - X - X - ... - X - X - []
|
Y - X - X - ... - X - X - []
|
[]



Dada una posición cualquiera (x, y), debe iterarse "y" veces sobre la lista "Y" y luego iterarse "x" veces sobre la sublista "X", para llegar a la posición a actualizar.

Supuesto que la posición se elige uniformemente entre todas las posibles "(1, 1) - (size, size)"; entonces la longitud promedio es "size/2 + size/2" es decir "size", que es precisamente la raíz cuadrada del número de nodos.


En cuanto a referencias, la obvia es el propio Haskell, yo he implementado el recorrido de las listas (me parece más elegante, sencillo y visual las veces que se itera), pero podría haberse hecho usando las librerías de Haskell para recorrer listas. Una forma (sin testear, escrita al vuelo) podría ser (de la función "a"):

addOne data (x, y) = prevY ++ addY ++ posY'
  where (prevY, posY) = splitAt (y - 1) data
        curY = head posY
        posY' = tail posY
        addY = prevX ++ [value + 1] ++ posX'
        (prevX, posX) = splitAt (x - 1) curY
        value = head posX
        posX' = tail posX


Los costes de recorrer las listas usando "Data.List" no vienen indicados (que raro, en "Data.Text" y otros sí vienen) excepto para "nub" con coste cuadrático O(n^2). Pero del código fuente se ve en la implementación (genericSplit, genericTake, etc... que son las instanciadas como indica la doc) itera de la misma forma que mi función "a" (o mi función como estos generic).

En Adjacency list también dejan claro que recorrer la lista completa (una fila) tiene coste O(n).
0votos

Escrito por jneira hace 6 años

Mil gracias por tu paciencia pedagogica.
0votos

Escrito por josejuan hace 6 años

De las discusiones se aprende mucho, tanto si al final tienes la razón como si no o tanto si eres el que escuchas como el que dices, la cuestión es comentar, hablar y compartir lo que sepamos. ;)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.