• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

eMineiro

Ajuda - Tipos

8 mensagens neste tópico

Tenho o seguinte código:

data Nn = 
Z
|S Nn
deriving(Eq,Read,Show)

-- Converte Nn pra int

toNn Z = 0
toNn (S x) = 1 + toNn x

-- Funcoes soma

itsum m Z = m
itsum m (S n) = itsum (S m) n

recsum m Z = m
recsum m (S n) = (S (recsum m n))

Queria saber qual metodo vocês usam para saber qual função é melhor , se é a itsum ou recsum , no haskel existe :let +s e me informa o tempo que demorou a ser executada certa função, porém nao há um modo menos computacional de analisar isto??

Se os senhores pudessem me ajudar o professor me pediu para passar esse código para C , porém nao encontro alternativas de faze-lo , eu teria que usar o typdef?? plzz help me

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dava jeito explicar o código...

Quanto à eficiência, talvez a primeira seja mais eficiente pois tail recursive, e é mais fácil de optimizar pelo compilador. Esquecendo optimizações, parece-me que ambas demoram sensivelmente o mesmo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bom, foi criado um tipo Nn , que tem como elementos , o Z (elemento incial) e todos os outros sao derivados atraves dele atraves do operador S, ou seja S Z é um elemento do tipo Nn, (S (S Z)) também é um elemento do tipo Nn.

A função itsum e recsum são iguais (só nao sei qual é mais rapida), e elas fazem a soma de um tipo Nn por outro tipo Nn.

[  Ex.: (S Z) + Z =  (S Z) ... (S (S Z) + (S Z) = (S (S (S Z)))  ]

Se eu fizer manualmente e verificar quantas vezes é chamda tal função , se em um dos casos tal função for chamada mais vezes eu posso afirmar que ela é pior?(Estou nessa dúvida pq existe os metodos de ordenações que em alguns casos sao ruins mas em outros sao extremamente eficientes)

Passar isso para C está me dando dor de cabeça tb, como eu crio um tipo em C

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para converter para C, depende se queres manter a estrutura recursiva ou não. Se for para manter, vais ter que usar apontadores...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ambas as funções são equiparáveis. Depende é para o que quiseres.

A função itsum é mais eficiente em termos de memória já que não constrói o número todo na memória mas vai passando como acumulador.

A segunda função já vai pondo todos os passos intermédios na memória, ela é pior em memória mas em termos de lazy é melhor. Tipo se de seguida à soma chamares uma função que verifica se é zero ou não a recsum só vai "processar 1 passo".

Portanto depende mesmo para o que tu queres, mas o mais provável é ser o itsum que queres, já que é mais amiga do programador. Com a recsum podes facilmente dar "stack overflow".

Em relação a traduzir para C, se quiseres uma tradução directa. Esse tipo de Haskell transforma-se numa struct com uma flag e com uma union. Mas para um tipo de dados tão simples, não precisas de algo tão detalhado. Como o Rui Carlos disse aqui um apontador funciona às mil maravilhas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigado pessoal.

Outra coisa , meu professor pediu que eu provasse que.:

toNn (itsum m n) = toNn m + toNn n

Quebrei a cabeça e fiz aqui uma prova , vejam se ficou bom ou ruim:

para n = Z, temos:

(itsum m n) = m    E      toNn n = 0

substituindo temos que,

toNn m = toNn m + 0.

O mesmo vale para m = Z.

Para m e n = m (S n) , temos:

1 - toNn (istum m (S n)) = toNn m + toNn (S y)

2 - toNn (itsum (S (m)) n) = toNn m + 1 + toNn n

se n = Z

toNn (S m) = toNn m + 1 + 0

1 + toNn m = 1 + toNn m

Verificamos que ao incrementarmos em S ao valor de n , independentemente

do valor de m , ambas os lados se incrementam de 1 ao final o que torna

a equação sempre verdadeira.

Eu achei que a explicação ficou QUASE uma prova, mas o final ficou meio estranho , preciso de opiniões.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Normalmente isso prova-se por indução.

Provas para o caso base, ou seja, para quando o n = Z (que já demonstraste).

E agora provas que caso se para o n for verdade então também terá de ser verdade para (S n).

Hipótese de indução: toNn (itsum m n) = toNn m + toNn n

Vamos demonstrar que toNn (itsum m (S n)) = toNn m + toNn (S n)

- Por definição de toNn

toNn (itsum m (S n)) = toNn m + 1 + toNn n

- Por definição de itsum

toNn (itsum (S m) n) = toNn m + 1 + toNn n

- Por definição de itsum (se fosse recsum era mais óbvio, não sei se no caso de itsum uma pessoa pode fazer esta salto directamente)

toNn (S (itsum m n)) = toNn m + 1 + toNn n

- Por definição de toNn

1 + toNn (itsum m n) = toNn m + 1 + toNn n

- Hipotese de indução

1 + toNn m + toNn n = toNn m + 1 + toNn n

e prontos, é verdade.

Já estou um pouco enferrujado a provar as cenas, mas acho que é algo deste género.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Me lembrei de indução hoje, estou treinando muito essas provas , pois tenho uma materia na faculdade --> Estrutura de Dados em que me parece que os testes valendo pontos irão ter exercícios deste tipo , provar que algo é igual a outro.E o método de indução é sempre usado.

Como você pulou um passo vou tentar sozinho aqui provar que istum (S  m) n = (S (itsum m n)), caso eu não consiga  virei aqui pedir ajuda xD

O site do portugal-a-programar é o único site que conheço(no idioma portugues)  que existe pessoas disposta a nos ajudar em haskell, afinal é uma linguagem pouco conhecida, obrigado pela força.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora