fnds 2 Denunciar mensagem Publicado 13 de Maio de 2010 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. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Rui Carlos 348 Denunciar mensagem Publicado 13 de Maio de 2010 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. Rui Carlos Gonçalves Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
fnds 2 Denunciar mensagem Publicado 13 de Maio de 2010 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. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Rui Carlos 348 Denunciar mensagem Publicado 13 de Maio de 2010 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 Rui Carlos Gonçalves Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
fnds 2 Denunciar mensagem Publicado 13 de Maio de 2010 Ah Map, pensava que era a função map :X Vou ver o código, obrigado. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Triton 10 Denunciar mensagem Publicado 14 de Maio de 2010 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 <3 life Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Betovsky 2 Denunciar mensagem Publicado 14 de Maio de 2010 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... "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
fnds 2 Denunciar mensagem Publicado 14 de Maio de 2010 @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. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Betovsky 2 Denunciar mensagem Publicado 14 de Maio de 2010 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... "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Betovsky 2 Denunciar mensagem Publicado 2 de Junho de 2010 E então? Sempre conseguiste por isso a funcionar? "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
fnds 2 Denunciar mensagem Publicado 2 de Junho de 2010 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 Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Betovsky 2 Denunciar mensagem Publicado 3 de Junho de 2010 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 "Give a man a fish and he will eat for a day; Teach a man to fish and he will eat for a lifetime. The moral? READ THE MANUAL !" Sign on a computer system consultant's desk Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
fnds 2 Denunciar mensagem Publicado 11 de Junho de 2010 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. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites