Q2 - Ainda em relação a 'splay', estamos com dificuldade em construir o gene do catamorfismo que é pedido. Podem dar alguma ajuda?

R: Pensem assim (e aqui verão a vantagem de se pensar a programação com funções de ordem superior): a) o tipo de saída BTree a -> BTree a sugere que o resultado do cata deve ser uma transformação de árvores; b) Se a lista de entrada for vazia não há transformação nenhuma a fazer; c) Se o gene for [g1,g2], em g2(b,f) devem considerar que f é a acumulação de todas as transformações que foram feitas tendo a cauda a lista em consideração. g2 deverá acrescentar a essa transformação já efectuada algo mais, de acordo com b.

Q3 - Quando nos cálculos passamos 'in' (resp. 'out') de um tipo para 'out' (resp. 'in') a mesma posição do outro lado de uma igualdade, que lei(s) estamos a aplicar? Vêm no formulário?

R: Estamos a aplicar as leis (2.18, 2.19) dos apontamentos. Essas leis são válidas para qualquer isomorfismo f/fº, não apenas para in/out. Não, estas leis não estão no formulário.

Q4 - É possível existirem estruturas que possuem functores com mais de 2 parâmetros? Se por exemplo eu estiver a trabalhar com uma estrutura paramétrica nos tipos A e B, faz sentido um functor triplo? E se sim, como o representaríamos na forma B(f,g,h) em que eg. A --f--> C e B --g-->D ?

R: Sim - veja-se por exemplo baseExp no módulo Exp.hs do trabalho prático.

Q5 - Estamos a sentir bastantes dificuldades na função de inserção no problema do dicionário e ainda não conseguimos ter nem o princípio de uma solução. Não será possível darem-nos uma orientação sobre por onde começar?

R: Para definir a função dic_in de uma palavra e seu significado no dicionário, o melhor é pensarem que vai ser preciso fazer recursividade "horizontal" - à procura da primeira letra - e "vertical" - descida para inserir o resto da palavra e seu sinónimo. O mais natural será assim pensar num hilomorfismo auxiliar que aceite a palavra e a lista de expressões onde está a ser feita a procura / inserção. Recomenda-se que pensem na solução com base num diagrama com os tipos em jogo antes de passarem à programação. Como é habitual em problemas deste género, a parte "ana" do "hilo" vai fazer a maior parte do trabalho.

Q6 - Estamos com dificuldades em fazer a função 'splay' como catamorfismo de listas. Isto porque não conseguimos ver como o fazer sem navegar pela árvore. Será que nos podem dar alguma pista?

R: Têm toda a razão! A função splay deveria ter tipo BTree a -> [Bool] -> BTree a e ser um catamorfismo de BTree e não de listas. Se não conseguirem escrevê-lo directamente, escrevam primeiro a versão uncurried - que, com tipo (BTree a, [Bool]) -> BTree, não é um catamorfismo - e depois tentem derivar daí a solução final.

Q7 - O que deve ser apresentado no trabalho prático além das funções, claro, e dos diagramas explicitamente requisitados? Todos os diagramas? Todos os cálculos para a obtenção das funções e funtores? Comentários explicando funcionalidades do código?

R: Isso é deixado ao vosso critério, pois podem ter ou não tempo para escrever explicações sobre as vossas soluções. Se tiverem tempo, isso é bom e será valorizado. Mas esses textos devem ser objectivos e não devem distrair o avaliador do essencial, ok? Podem também ajudar quando tiverem mais do que uma solução e queiram compará-las. Podem usar \begin{spec}...\end{spec} para código que que querem formatar como em \begin{code}...\end{code} mas não querem que seja executado.

Q8 - Tenho uma dúvida depois do que li na Q6 acima: os professores irão atualizar o enunciado e o trabalho com o quickCheck/splay corrigido ou terão de ser os grupos a mudar?

R: A nossa regra é evitar mudar o enunciado enquanto o trabaho está a correr. O que devem fazer é (a) não mexer no tipo de splay, por forma a estar compatível com o QuickCheck, etc; (b) definirem splay = flip ⦇ g ⦈, em que ⦇ g ⦈ é o catamorfismo de BTree de acordo com o que se escreveu na Q6.

Q9 - Estamos com dificuldade em abordar a primeira questão. Será que nos podem dar mais informação sobre este tipo de dicionários em árvore?

R: Sim. Sugerimos que consultem, por exemplo, esta página na wikipédia: https://en.wikipedia.org/wiki/Trie.

Q10 - Nós definimos a função maisDir = ⦇ [nothing, π2.π2] ⦈ que tipa bem mas dá sempre Nothing. Não estamos a ver como não perder o "último elemento" da árvore, mais à direita...

R: A vossa solução tem, no caso recursivo, g2 = π2.π2, que é a mesma coisa que g2(a,(x,y)) = y. Têm de pensar num g2 que não seja "tão rápido" a deitar o 'a' fora. Ora vejam lá...

Q11 - Quando fazemos testes das propriedades 9, 10 e 11, estes nunca terminam. Sendo assim, gostaríamos de saber se há algo que se possa alterar nos testes de maneira a ser possível testar as referidas propriedades.

R: O QuickCheck (que opera sobre um mónade) pode gastar bastantes recursos quando as estruturas são árvores etc, pois começa a tomar a iniciativa de criar casos de teste arbitrariamente complexos. No fim da secção 3 do enunciado tem como controlar o número de casos de teste e a sua complexidade. Façam experiência usando maxSuccess e maxSize, começando por valores baixos e aumentando.

Q12 - Podemos resolver o exercício 5 puramente em código Haskell "normal", ou seja, sem catamorfismos, eithers, etc que aprendemos na disciplina?

R: O objectivo principal desse exercício é praticarem com mónades num problema concreto. O formato de resolução é “livre”.

Q13 - No problema 1, a propriedade 1 tem a pré-condição de ser testada apenas para dicionários normalizados. Sendo assim, não deveria a propriedade 3, que é também aplicada a dicionários exportados, ter a mesma pré-condição? Pergunto isto porque nos testes da 3ªa propriedade aparecem dicionários não normalizados.

R: Tem razão e obrigado pela pergunta, pois o problema é interessante (irão seguramente reencontrá-lo mais tarde na vossa vida profissional...): (a) é feita um representação em memória para obter eficência; mas (b) "teoricamente" a memória só será "habitada" por árvores de dicionários normalizados, após importação.

Contudo, o Quickcheck não sabe disso e começa a gerar representações em memória "absurdas", pois não há nenhum dicionário normalizado que as origine. A gente olha para elas e pensa: "não vou ligar porque isto nunca iria acontecer na realidade". Mas há contra-exemplos e a gente não gosta disso...

A alternativa é fazer com que os testes filtrem situações absurdas. Mas, como não podem mudar o enunciado a não ser no anexo onde estão a escrever as vossas soluções, a solução é adicionarem estes novos testes à vossa resolução e mostrarem na oral que as vossas funções os satisfazem:

\begin{code}
valid t = t == (dic_imp . dic_norm . dic_exp) t
\end{code}
\begin{propriedade}
Se um significado |s| de uma palavra |p| já existe num dicionário normalizado então adicioná-lo
em memória não altera nada:
\begin{code}
prop_dic_red1 p s d
   | d /= dic_norm d = True  
   | dic_red p s d = dic_imp d == dic_in p s (dic_imp d)
   | otherwise = True
\end{code}
\end{propriedade}
\begin{propriedade}
A operação |dic_rd| implementa a procura na correspondente exportação de um dicionário normalizado:
\begin{code}
prop_dic_rd1 (p,t)
   | valid t     = dic_rd  p t == lookup p (dic_exp t)
   | otherwise = True
\end{code}
\end{propriedade}

Já agora ficam a saber mais alguma coisa: em "teoria de desenvolvimento de software" (normalmente chamada "métodos formais"), dic_norm diz-se ser um invariante e valid diz-se ser um invariante de representação.

Q14 - Que grau de confiança na correcção do nosso código podemos ter usando o QuickCheck?

R: É sempre relativa. Os testes validam determinadas propriedades desejáveis de um programa, não todas... e portanto nunca provam que um programa está absolutamente correcto. Podem é provar que está incorrecto! Leiam a célebre frase de Dijkstra:

Program testing can be used to show the presence of bugs, but never to show their absence!

É por isso que uma disciplina como CP se justifica - conseguimos provar propriedades desejáveis dos programas sem fazer testes, usando as leis do cálculo da programação funcional.

Q15 - Conseguimos implementar as funções di_rd e dic_in em Haskell "standard", mas não conseguimos até agora convertê-las em hilomorfismos, como se refere na FAQ5. Vale alguma coisa apresentarmos o que temos, se não tivermos tempo de fazer essa conversão?

R: É sempre melhor apresentar o que têm do que não apresentar nada. E pode ser que até à oral possam ter tempo para as converter em hilos e mostrar lá que o acabaram por fazer com sucesso...

Q16 - Onde posso ler mais sobre isso de invariantes, invariantes de abstracção, etc?

R: Se procurarem "what are invariants" ou coisa do género na internet obtêm muita coisa, por exemplo What are invariants, how can they be used, and have you ever used it in your program?

Nos vossos apontamentos nós parámos no capítulo 4; mas se continuarem pelo 5, 6 e em particular o 7, têm lá a teoria de que se falou acima. Aqui na UM, essa matéria é dada no perfil MFES.

Q17 - No decurso do trabalho surgiram-nos estas dúvidas: tendo-se uma função recursiva k que tem uma cláusula k([],a) = a, tem-se curry k [] a = a e logo curry k [] = id, certo? E se o que tivermos for k(a,[]) = a, a função g = curry k a vai ser tal que a = g [], é assim?

R: Sim + sim . No primeiro caso reparem na lei (73) do formulário. No segundo caso, a situação descrita quer dizer que, onde tiverem a, podem sempre substituir por g [], se vos der jeito...

Q18 - Professores: para submeter o trabalho é necessário apenas um elemento o fazer ou todos os elementos do grupo tem de submeter?

R: Basta um elemento do grupo submeter.

Q19 - É possível resolver a insOrd das BTrees por recursividade mútua? Não nos está a fazer muito sentido sem ser por anamorfismo...

R: Não queremos dizer que não possa resolver como anamorfismo. Mas o que se pede é que seja um cata. Pensem assim: (a) caso árvore vazia - é imediato; (b) caso recursivo - o gene vai receber um elemento e duas sub-árvores. Imaginem que o valor à entrada já foi inserido algures numa delas, como que "por milagre"... O que é que o gene deve fazer se se assumir isso? Mais não podemos dizer...

Q20 - Estava a tentar submeter o trabalho e recebi o erro de que o meu número não se encontra em nenhum grupo... Mas na página de alunos está lá! Devo escrever o "a" antes dos dígitos ou não?

R: Devem escrever só o número. Nalguns grupos houve trocas. Nesse caso, quem deve submeter o trabalho é um elemento do grupo que não tenha feito trocas, ok?

Q21 - Eu já passei em época normal à UC, mas queria saber se posso efectuar o exame de recurso de amanhã, dia 18, para fazer melhoria. Ou seja, se fico com a melhor nota ou com a nota do exame de recurso.

R: Este ano, excepcionalmente, qualquer aluno pode fazer melhoria. A nota será t = max(normal, recurso). O que a equipa docente pede é que, caso o aluno veja que não vai mesmo dar para subir nota, não submeta o exame. Poupar-se-ão recursos que podem preciosos noutras circunstâncias (atender alunos, etc). Obrigado pela vossa colaboração.

Q22 - Num passo dum teste resolvido aparece B(a,b) . B(c,d) = B(a . c , b . d), onde B é um bifunctor. Isto encontra-se no formulário?

R: Não. Mas essa lei - que é a (3.57) dos apontamentos - é a extensão a bifunctores da lei functorial (41) do formulário. Já agora: B(id,id)=id é a correspondente extensão da lei (42).

Q23 - Alguns colegas estão a dizer que quem teve R na pauta de Julho pode ir a época especial. No nosso grupo tivemos R por não termos nota mínima no trabalho. É possível esclarecerem quais os critérios para ir a época especial?

R: Devido à situação anormal que vivemos, no corrente ano lectivo foi dado acesso generalizado à época especial. Contudo, esse acesso geral não tem - nem pode ter - enm consideração os regimes de avaliação particulares de cada disciplina. Em CP esse regime determina notas mínimas para passar de ano nas componentes T e TP. O exame de recurso permite melhorar a nota T mas não a nota TP. Logo, se um aluno não tiver nota mínima no TP, o exame de recurso não lhe vai permitir passar à disciplina, pois a nota TP permanece a mesma.