"Cache" em Haskell

[fnds 2]

Boas.

Estou a resolver um problema em que precisava de fazer cache de determinados valores para evitar executar a mesma função com os mesmos argumentos várias vezes, se fosse noutra linguagem criava uma lista/array/dicionario e colocava lá os valores, mas em Haskell não estou a ver.

Já estive a ler sobre memoization (http://www.haskell.org/haskellwiki/Memoization) mas sinceramente, não percebi nada.

Cumprimentos.

[Rui Carlos 348]

O compilador normalmente já faz esse tipo de optimizações.

Como o Haskell é uma linguagem funcional, o resultado de uma função aplicada aos mesmos argumentos é sempre o mesmo, por isso ele sabe que os podes guardar (embora nunca se saiba quando ele os está mesmo a guardar).

A alternativa será as funções receberem sempre um Map com os valores previamente calculados, e antes de tudo começar por ver se o valor que se quer já está no map.

É claro que isto torna a funções um pouco menos elegantes porque precisas de acrescentar mais um argumento e um resultado (tipo, f::X->Y->Z  ----> f::Map (X,Y) Z->X->Y->(Map (X,Y) Z,Z)).

Para evitares isto, podes usar monads de estado, mas isto já é um assunto um pouco complexo.

[fnds 2]

Parece complexo, consegues dar um exemplo com o tal map?

Já estive a tentar fazer algo como está aqui (http://www.haskell.org/haskellwiki/Memoization)  no exemplo da sequência de Fibonacci  mas sem sucesso.

[Rui Carlos 348]

O Map é uma estrutura de dados do género de um dicionário (e que é usada para guardar a cache).

A implementação da função potência devia ficar mais ou menos isto:

-- sem cache
power1::Int->Int->Int
power1 x y=x^y

-- com cache
power2::Map (Int,Int) Int->Int->Int->(Map (Int,Int) Int,Int)
power2 cache x y=
  let tmp=lookup (x,y) cache
  in case tmp in
        Nothing -> (insert (x,y) x^y,x^y)  -- o valor não está na cache; calcular valor, colocá-lo na cache, e devolver valor e nova cache
        Just z -> (cache,z) -- o valor está na cache; devolver valor e cache antiga, visto que não foi modificada

-- 2^x+2^x+3^x+3^x
prog :: Int -> Int
prog x =
  let (c1,r1)=power2 empty 2 x   -- calcula e adiciona à cache
      (c2,r2)=power2 c1 2 x    -- já está na cache
      (c3,r3)=power2 c2 3 x    -- calcula e adiciona à cache
      (c4,r4)=power2 c4 3 x    -- já está na cache
  in r1+r2+r3+r4

-- fibonacci
fib_aux ::Map Int Int->Int->(Map Int Int,Int)
fib_aux cache x=
  let tmp=lookup x cache
  in case tmp in
        Nothing ->
          let (c1,fib1)=fib_aux cache (x-1)
              (c2,fib2)=fib_aux c1 (x-2)     -- aqui o valor deverá sempre vir da cache, pois ao calcular para x-1 vamos colocar na cache (c1) o valor para x-2
          in (insert x (fib1+fib2) c2,fib1+fib2)
        Just y -> (cache,y)

fib n=fib_aux empty n

Acabei por fazer também o fibonacci.

PS: Não testei o código

[fnds 2]

Ah Map, pensava que era a função map :X

Vou ver o código, obrigado.

[Triton 10]

Haskell

Não percebo nada da linguagem, mas estive a ver o código do Rui Carlos e parece fixe

Desculpa lá a invasão no tópico fnds

[Betovsky 2]

Por acaso estava/estou a escrever um artigo para a revista sobre programação dinâmica em Haskell. Infelizmente devido à falta de tempo ficou parado no tempo. Se puderes dá uma vista de olhos. Está inacabado mas já aborda o problema e tem o Fibonacci como exemplo.

http://wiki.portugal-a-programar.org/revistaprogramar:programacao_dinamica_em_haskell

É mais simples e menos poderoso que o uso do Map, pode ser que te ajude a compreender melhor.

Qualquer dúvida já sabes...

[fnds 2]

@triton

Na boa

Olha a linguagem é mesmo fixe, é muito fácil e rápido aprender o básico, enquanto não complicares é um espectáculo

Eu estava a resolver o tal problema em Python e como envolvia várias listas pensei "isto em Haskell era um mimo", fiz a mesma cena com 1/3 do código. Agora quando precisei da tal cache é que me lixei lol

@Rui Carlos

Já percebi a ideia, não percebi é o o porquê de usar o Map em vez de uma simples lista [(x,y), z].

O código não corre, mas não é grave.

@Betovsky

O que escreveste no artigo está exclarecedor, depois fala lá também dos exemplos que estão aqui http://www.haskell.org/haskellwiki/Memoization

Vou agora tentar usar os Arrays.

[Betovsky 2]

Já percebi a ideia, não percebi é o o porquê de usar o Map em vez de uma simples lista [(x,y), z].

O problema de usar uma lista é devido à performance do lookup (O(n) pra lista; O(log n) pro Map).

No caso dos Arrays é O(1) só que estás limitado nos tipos a indexar a informação, ou seja, não dá para todos os casos...

[Betovsky 2]

E então? Sempre conseguiste por isso a funcionar?

[fnds 2]

Não acabei por desistir, estava a dar muito trabalho então resolvi o problema em Java.

O problema é este: http://code.google.com/codejam/contest/dashboard?c=188266#

A solução sem cache é muito simples em haskell.

Já agora a minha solução bruta:

import Text.Printf

main = do x<-getContents
         run x

--input/output
strToBase :: String -> Int
strToBase "2" = 2
strToBase "3" = 3
strToBase "4" = 4
strToBase "5" = 5
strToBase "6" = 6
strToBase "7" = 7
strToBase "8" = 8
strToBase "9" = 9
strToBase "10" = 10

parseInput :: String -> [[int]]
parseInput str = tail (map (\x-> map strToBase (words x)) (lines str))

printRes :: [[int]] -> Int -> IO()
printRes [] _ = return ()
printRes (l:ls) n = printf "Case #%d: %d\n" n (lowMultiBaseHappy l)
             >> printRes ls (n+1)

run :: String -> IO()
run str = printRes (parseInput str) 1

--calculate
dec2baseB :: Int -> Int -> [int]
dec2baseB 0 _ = []
dec2baseB n b = (n`mod`b: dec2baseB (n`div`b) b)

happiness :: Int -> Int -> [int] -> [int]
happiness n 2 ls = [1]
happiness n b ls | elem n ls = [0]
                | next==1 = [1]
                | otherwise = happiness next b (n:ls)
                where next = sum (map (^2) (dec2baseB n b))

isHappy :: Int -> Int -> Bool
isHappy n b | v==0 = False
           | v==1 = True
           where [v] = happiness n b []

multiBaseHappy :: Int -> [int] -> Bool
multiBaseHappy n ls = and (map (isHappy n) ls)

firstMultiBaseHappy :: Int -> [int] -> Int
firstMultiBaseHappy n bases | multiBaseHappy n bases = n
                           | otherwise = firstMultiBaseHappy (n+1) bases

lowMultiBaseHappy :: [int] -> Int
lowMultiBaseHappy bases = firstMultiBaseHappy 2 bases

[Betovsky 2]

Usando o teu código como base.

import Prelude hiding (lookup)
import Text.Printf
import Data.Map hiding (map)

type HappySet = Map (Int,Int) HappyState
data HappyState = OK | NOK | Maybe

main = getContents >>= resolve

resolve = printRes 1 . run empty . parseInput

run :: HappySet -> [[int]] -> [int]
run  _   []    = []
run set (l:ls) = let (num, set') = seekHappy 2 l set
                in num : run set' ls

parseInput :: String -> [[int]]
parseInput = map (map read . words) . tail . lines

printRes :: Int -> [int] -> IO()
printRes _ [] = return ()
printRes n (l:ls) = printf "Case #%d: %d\n" n l >> printRes (n+1) ls

dec2baseB :: Int -> Int -> [int]
dec2baseB 0 _ = []
dec2baseB n b = (n`mod`b: dec2baseB (n`div`b) b)

seekHappy :: Int -> [int] -> HappySet -> (Int, HappySet)
seekHappy n bases h = fun $ isMultiBaseHappy n bases h
  where fun (check, h') | check = (n, h')
                        | otherwise = seekHappy (n+1) bases h'

isMultiBaseHappy n bases h = foldr fun (True, h) bases
  where fun   _  r@(False, set) = r
        fun base   (_    , set) = isHappy base n set

isHappy  _   1 set = (True, set)
isHappy base n set = case (lookup (base,n) set) of
                      Just OK    -> (True , set)
                      Just NOK   -> (False, set)
                      Just Maybe -> (False, set)
                      Nothing    -> let (check, set') = isHappy base next (insert (base,n) Maybe set)
                                    in if check then (True , insert (base, n) OK  set')
                                                else (False, insert (base, n) NOK set')
  where next = sum $ map (^2) $ dec2baseB n base

[fnds 2]

Obrigado Betovsky

Vou analisar o teu código com calma e percebe-lo bem, é que ainda tenho *muito* haskell para aprender, ainda só sei o básico.